Die Geschichte von Nowosibirsk steht in engem historischem Zusammenhang mit der Erschließung Westsibiriens. Die Urzelle der Stadt entstand 1893 in Folge der Errichtung der Transsibirischen Eisenbahn. Die Siedlung hieß zunächst Nowaja Derewnja (Neues Dorf), Gussewka, Kriwoschekowski, Alexandrowski, Nowo-Nikolaewski, bis sie 1903 mit den Stadtrechten den Namen Nowonikolajewsk (Новониколаевск, nach dem Namen des letzten Zaren Russlands) erhielt. 1925 wurde die Stadt in Nowosibirsk umbenannt.
Alexander III. begann im späten 19. Jahrhundert mit dem Bau der Transsibirischen Eisenbahn (1890–1900), um eine interne Verkehrsverbindung zum Anschluss der sibirischen Region mit ihrem Reichtum an Bodenschätzen an Moskau und Westrussland zu gewährleisten. Die Verbindung sollte an der alten Stadt Kolywan den Fluss Ob überqueren, jedoch wurden die Pläne geändert, sodass die Brücke bei dem kleinen Dorf Kriwoschokowo errichtet wurde. Da hierzu sehr viele Eisenbahnarbeiter notwendig waren, entstand schnell die Siedlung Nowonikolajewsk direkt in der Nähe der Brücke. Der Name steht in Beziehung zu Zar Nikolaus II..
Das offizielle Gründungsdatum ist die Grundsteinlegung der Brücke mit einem Gottesdienst am 20. Mai 1893. Im Frühjahr 1897 wurde die Brücke für den Verkehr geöffnet, der Bahnhof mit Infrastruktur bestand schon. Da die umliegenden Siedlungen diese Möglichkeit schnell für den Transport ihrer Güter über größere Entfernungen nutzten, erweiterte die Stadt sich zusehends. Nowonikolajewsk hatte zu diesem Zeitpunkt bereits 7.800 Einwohner.
Im Dezember 1903 bekam Nowonikolajewsk den offiziellen Status als Stadt. Inklusive der Bevölkerung der Umgebung hatte es bereits 22.000 Einwohner. 1906 wurde die erste sibirische Bank in Nowonikolajewsk gegründet. 1915 waren es schon fünf Banken. Schnell wurde die Stadt das Finanz- und Handelszentrum der Region. 1907 bekam sie alle Rechte auf Selbstverwaltung zugesprochen. Die Einwohnerzahl betrug inzwischen 47.000. Kurz vor der Oktoberrevolution hatte die Stadt bereits 80.000 Einwohner und war die größte Industriestadt, die nicht allein im Agrarsektor industriell entwickelt war, mit mehr als 40 Schulen, Kinos, einer Hochschule, einer Schiffswerft und mehr als 8 Kirchen.
1917 übernahmen Arbeiter und Soldaten die Stadt. Nowonikolajewsk wurde ein wichtiger strategischer Punkt für die Armee Koltschaks (500.000 Soldaten) in den Bürgerkriegsunruhen, wurde jedoch 1919 von der Roten Armee erobert. Die Brücke wurde zerstört, und die Stadt litt unter den Folgen des Bürgerkrieges. Cholera, Typhus und andere Epidemien kosteten Tausenden das Leben. Nowonikolajewsk war in der für die UdSSR schwierigen Anfangszeit eine der wenigen Städte, in denen es an nichts fehlte. 1921 wurden unter Lenin Verwaltungseinrichtungen von Omsk nach Nowonikolajewsk verlagert, und die Stadt wurde die Hauptstadt der Region.
1925 wurde die Stadt auf Wunsch der Einwohner in Nowosibirsk (frei übersetzt „Neues Sibirien“) umbenannt, wie sie auch heute noch heißt. Unter Stalin veränderte sich die Stadt und wurde hauptsächlich zu einem Industriezentrum. Als Handelszentrum verlor sie an Bedeutung. Viele der neuen Industriezweige hatten ihren Schwerpunkt im Agrarsektor.
Während der Hungerperiode 1932–1933 kamen mehr als 170.000 Flüchtlinge nach Nowosibirsk und ließen sich in Slums am Rande der Stadt nieder, die heute große Stadtteile sind. Zwischen 1940–42 wurden mehr als 50 industrielle Fertigungsanlagen von Westrussland nach Nowosibirsk verlagert, und die Stadt wurde ein Rüstungszentrum der Roten Armee. Mehr als 140.000 Flüchtlinge hielten sich zeitweilig in der Stadt auf. Zwischen 1915 und 1945 entstanden mehr als 26 Militärkrankenhäuser in Nowosibirsk.
Nowosibirsk wurde zum Hauptverkehrsknotenpunkt Sibiriens als Verbindung zwischen West und Ost. 1943 wurde die sibirische Abteilung der Akademie der Wissenschaften in Nowosibirsk eröffnet. Ab diesem Zeitpunkt ist Nowosibirsk auch die wichtigste Bildungsstätte Sibiriens. 1954 wurde die Straßenbahn gebaut, Nowosibirsk hatte 287.000 Einwohner. 1955 wurde die Hauptbrücke über den Ob, die „Kommunalni-Brücke“, gebaut.
1957 wurde der Ob-Stausee (1070 km² Fläche, maximal 8,8 Mrd. m³ Stauinhalt) zum Zweck der Stromgewinnung (1687 Mio. kWh im Jahresdurchschnitt) gebaut. Dies hatte weitere Umweltprobleme zu den bereits durch die starke Industrialisierung verursachten zur Folge. Erosion aufgrund vernichteter (überfluteter) Wälder, Überflutungen und Hochwasser traten auf.
Auch an den Ufern des Ob-Stausees wurde 1957 Akademgorodok, die Stadt der Wissenschaft, errichtet (ca. 30 km südlich vom Stadtzentrum) und wurde Zentrum der sibirischen Abteilung der Akademie der Wissenschaften. Dort entstanden innerhalb kürzester Zeit 14 Forschungseinrichtungen und Universitäten, quasi eine neue Stadt. Anfang der 60er-Jahre erreichte Nowosibirsk eine Größe von mehr als einer Million Einwohnern. 1979 wurde mit dem Bau der Metro begonnen, eröffnet wurde die erste Linie 1985.