Archäologische Funde aus dem 13. Bezirk (Titlgasse) zeigen, dass schon während der Altsteinzeit Menschen das Gebiet begangen haben. Funde im Stadtgebiet und im Umland beweisen, dass ab der Jungsteinzeit das Wiener Becken kontinuierlich besiedelt war. Die begünstigte klimatische Lage und fruchtbaren Böden Wiens boten den jungsteinzeitlichen Bauern gute Siedlungsmöglichkeiten. Darüber hinaus konnte der für die Steingeräteherstellung begehrte rötlichbraune und grünliche Hornstein in Wien bergmännisch (13. Bezirk, Roter Berg; 23. Bezirk, Mauer-Antonshöhe) im Tagbau gewonnen werden. Funde der Kupferzeit wurden ebenfalls in Wien nachgewiesen (6. Bezirk, U6-Station Gumpendorfer Straße; 13. Bezirk, Ober St. Veit–Gemeindeberg; 21. Bezirk, Eipeldauerstraße, Stadlau, 22. Bezirk, Aspern). Von der bronzezeitlichen Urnenfelderkultur zeugen in Wien etliche Brandgräber (19. Bezirk Höhenstraße/Leopoldsberg) aber auch Siedlungsspuren (23. Bezirk, Sulzengasse). Besonderheiten aus dieser Zeit sind Manipulationen an menschlichen Schädelfragmenten zu kultischen Zwecken. So wurde in einer spätbronzezeitlichen Abfallgrube (23. Bezirk, Sulzengasse) ein menschlicher Unterkiefer gefunden, dessen Gelenksköpfe entfernt wurden. Die ältere eisenzeitliche Hallstattkultur ist in Wien u. a. durch einen noch immer gut sichtbaren Grabhügel (21. Bezirk, Siemensstraße/Julius-Ficker-Gasse) und Siedlungsreste (10. Bezirk, Fontanastraße; 19. Bezirk, Leopoldsberg) vertreten. Funde am Leopoldsberg belegen eine Besiedlung ab der Bronzezeit, und vor allem ab der älteren Eisenzeit (Hallstattzeit). Die befestigte Höhensiedlung (Oppidum) datiert in die jüngere Eisenzeit, der Zeit der Kelten. Um Christi Geburt gelangte auch das heutige Wien unter römische Herrschaft und trat so erstmals in das Licht der Schriftgeschichte. An der Stelle des heutigen Wien entstand eine keltische Siedlung mit dem Namen Vedunia („Waldbach“). Im 1. Jahrhundert n. Chr. legten die Römer an der Stelle des heutigen Wiener Stadtzentrums nahe der Donau ein Militärlager (castra) mit der angeschlossenen Zivilstadt Vindobona (im heutigen 3. Gemeindebezirk) zur Grenzsicherung der Provinz Pannonien an. Noch heute kann man an den Straßenzügen des 1. Bezirks (Innere Stadt), den Mauerverlauf und die Straßen des Lagers erkennen. Die Lagermauer verlief entlang der Straßenzüge: Tiefer Graben, Naglergasse, Am Graben, Kramergasse, Rotgasse, Rabensteig und etwa parallel zum Salzgries. Durch den Verlauf der Donau wurde von der streng rechteckigen Grundform abgewichen. Damit erreichte das Lager eine Breite von ca. 455 m und eine Länge bis 500 m. Mit dem Bau des Legionslagers von Vindobona wurde um 97 n. Chr. begonnen. Die am Judenplatz archäologisch erforschten Kasernen waren zunächst aus Holz errichtet, zwischen den Kasernen verlief eine geschotterte Straße mit beidseitigen Abflussrinnen. Um 150 n. Chr. wurden sie durch Steinbauten ersetzt. Die Fundamente und tragende Innenmauern wurden mit Bruchsteinen und Mörtel hochgezogen. Für Trennmauern wurden ungebrannte Lehmziegel verwendet. Die Fußböden waren aus Lehm oder Mörtelestrich. Die Römer blieben bis ins 5. Jahrhundert. Das römische Legionslager lag weit im Osten des weströmischen Reiches und fiel daher den Wirren der germanischen Völkerwanderung rasch zum Opfer. Es gibt Hinweise auf ein katastrophales Feuer zu Beginn des 5. Jahrhunderts n. Chr. Die Überreste des Lagers wurden aber nicht verlassen, eine kleine Restsiedlung blieb zurück. Die Straßen und Häuser des frühmittelalterlichen Wien folgten dem Verlauf der römischen Lagermauern, Zentrum des frühen Wiens war der Berghof (heute Salvatorgasse). Die erste urkundliche Erwähnung im Mittelalter erfolgte 881 in den Salzburger Annalen, wo apud Weniam eine Schlacht gegen die Magyaren stattfand, wobei unklar ist, ob es sich um die Stadt oder um den Wienfluss handelt. Mit dem Sieg des ostfränkischen Königs Otto I. über die Magyaren im Jahr 955 in der Schlacht auf dem Lechfeld begann der Aufstieg Wiens wie auch Österreichs.