В разное время поселения на территории современного Новосибирска назывались по-разному. Первые два года - с 1893 по 1895 - будущий Новосибирск носил название - посёлок Кривощёковский. В октябре 1895 года сход жителей Кривощёковского выселка ходатайствовал о переименовании его в Александровский. Название это, впрочем, просуществовало недолго - местные жители вновь устроили сход, решив просить о новом переименовании - теперь уже в поселок Ново-Николаевский. В 1898 году прошение удовлетворили, а несколькими годами позже посёлку присвоили статус города. Ново-Николаевск, именно так, через дефис, назывался город до революции 1917 года. Затем дефис выбросили, а название стали писать слитно - Новониколаевск.
После смерти Ленина город предлагали назвать Новоленинск, Сибленинск, Ульяновск, Владлен и даже совершенно непроизносимое Ленинзнамёнск-на-Оби. Однако 12 февраля 1926 года Президиум ЦИК Союза ССР постановляет: «Переименовать город Новониколаевск в город Новосибирск».
Источник: https://nsknews.info/materials/mifosibirsk-kto-pervyy-nazval-gorod-novosibirskom-120157/
Рождение большого города
