През 1928 г. по предложение на кмета Владимир Вазов се взема решение за основаването на градски музей. Първоначално той съчетава задачите на градски музей, библиотека и архив. Наред с Народния, Военно-историческия и Църковно-археологическия, той е сред най-старите музеи на територията на столицата. В Правилника на музея е записано: „Да събира, проучва и пази ония предмети от материалната култура на София, които имат или ще имат значение за историята на София.”

​​​На 1 декември 1941 г. в сградата на пл. „Бански” № 3 се открива първата постоянна експозиция на музея.
По този повод вестник „Утро” отбелязва организирането на „Общински музей, който ще обхваща етнография, археология, стопанство, културен живот. Откриването на музея се счита за голяма културна придобивка.” За съжаление сградата просъществува много кратко – до бомбардировките по време на Втората световна война, когато е разрушена.

През 1952 г. музеят, библиотеката, архивът и градската художествена галерия се отделят като самостоятелни институции. През следващите десетилетия музеят развива многостранна дейност по опазване на културното наследство, но без музейна експозиционна площ, в тежки условия за съхраняване на ценностите от фонда. Междувременно той нараства и понастоящем наброява около 120 хил., като в тази бройка са включени и звената на Научната библиотека и Фотоархива. 

От 80-те години на XX век насам, наред с усилената събирателска дейност, са организирани над 120 временни изложби в страната и чужбина. Издадени са три тома на сборника „Сердика – Средец – София”, както и други научни и научно-популярни издания. Музеят редовно присъства в куултурния афиш на столицата.

През 1998 г. на основата на музея се създава Общинско предприятие „Стара София” със Софийски исторически музей (СИМ), на което се възлага да проучва, събира, опазва и стопанисва движимото и недвижимото културно наследство на територията на Столичната община.

През м. юни 2012 г. Общинско предприятие „Стара София” със СИМ е преобразувано в Общински културен институт (ОКИ) „Музей за история на София”.

Дълго нерешеният проблем с постоянната експозиция на Музея намира отговор с Решението на СОС от 1998 г. за адаптиране на сградата на Централната общинска минерална баня за музей на София.