Музей находится в особенном здании на набережной Оби в парке «Городское начало». Это памятник истории «Управление Томским имением Алтайского округа ведомства Кабинета Его Императорского Величества». Именно здесь в 1907 году были подписаны главные документы в жизни Ново-Николаевска (Новосибирска), после чего он и стал городом (нотариальный акт о выкупе императорских земель).

В 2016 году здание было передано Музею Новосибирска. После реставрации фасадов и реконструкции утерянных элементов ему был возвращен исторический облик.

Постоянная экспозиция «За много лет до Новосибирска: догородская история», подготовленная совместно с Институтом археологии и этнографии СО РАН, посвящена многовековой истории местности, на которой возник Ново-Николаевск — современный Новосибирск. Это стоянки и поселения древнего человека «Турист-2» и «Разъезд Иня-1» на правом берегу Оби, где жили люди времен неолита и поздней бронзы, левобережные русские села Кривощеково и Бугры, а также легендарное «Чертово городище», что находилось на территории нынешнего Октябрьского района.

Посетители увидят, как выглядели жители села Кривощекова — их облик реконструирован на основе черепов, найденных во время археологических работ, узнают, как возникали поселения на территории современного города. На выставке представлена одежда, обувь и домашняя утварь, нательные кресты кривощековцев, предметы, принадлежавшие жителям села Бугры, фотокопии уникальных документов.