Der har boet mennesker i Sisimiut-området gennem flere tusind år. I perioden ca. 2.400-500 f.v.t var området befolket af det palæo-inuitiske Saqqaq-folk. Herefter levede Dorset-folket langs denne strækning af den grønlandske vestkyst frem til omkring år 0. Siden var området ubeboet i en længere periode indtil Thulefolket, som er forfædrene til den nuværende grønlandske befolkning, kom hertil i det 14.-15. århundrede.
Byen Sisimiut blev grundlagt som dansk koloni i 1756. Kolonien var oprindelig anlagt på øen Ukiivik (Sydbay) nord for det nuværende Sisimiut, men på grund af dårlige fangst- og handelsmuligheder blev bebyggelsen i 1764 flyttet til sin endelige placering ved Ulkebugten og fik navnet Holsteinsborg efter missionskollegiets formand Grev Holstein.