Viedeň sa v dobe Keltov a Rimanov nazývala Vindobona, podľa keltského označenia Vedunia („lesný potok"). Názov Viedeň tak vôbec nesúvisí s vínom (v nemčine Wien a Wein). Keď Rimania v 5. storočí opustili túto oblasť, spomína sa mesto pod názvami Vindomina a Venia, po roku 1000 pod názvami Viennis a Wienne.

Čo sa v mladšej dobe kamennej 5000 rokov p. n. l. začalo tábormi vo viedenskej oblasti, napr. na vrchu Antonshöhe v lese Maurer Wald (dnes chránená prírodná oblasť) v 23. okrese, je dnes spolkovým hlavným mestom a zároveň samostatnou spolkovou krajinou: Viedeň. Kultúra podunajských krajín sa pritom vo všeobecnosti delila na západnú a východnú hlavnú skupinu. Zaujímavé je, že v dnešnej Viedni, napr. v Ober St. Veit (Viedeň 14) a vo Wertheimsteinpark (Viedeň 19) sa nachádzajú nálezy od oboch skupín. Skôr ako vzniklo mesto, bola oblasť Viedne bránou, ktorá spájala východ a západ.

Okolo roku 1800 p.n.l. sa dá vo viedenskej oblasti dokázať prítomnosť takzvaných ľudí zvonových pohárov, ktorých označenie je odvodené od typického tvaru ich keramiky s okrúhlym dnom. Osídlenou bola i mestská terasa, ktorú je možné rozoznať ako prudký zráz pri Maria am Gestade a Ruprechtskirche pri Donaukanali. 

Kostol Ruprechtskirche (vľ.) z 8. st. je najstarši zachovaný kostol vo Viedni. V ňom sa nachádzajú okenné tabuľe ešte z 13. st.; vpr.: Vykopávky na námestí Michaelerplatz odkryli časti "rímskeho základu Viedne"

Odkiaľ však pochádza pôvodný názov Viedne, je sporné. Isté je len jedno, že názov „Viedeň“ bol odvodený v procese trvajúcom celé tisícročie od názvu keltského osídlia. Niektorí zastávajú verziu, že názov "Viedeň" je odvodený od pomenovania „Vedunia" (lesný potok) z keltskej doby La-Téne v 4. storočí p.n.l. a vzťahuje sa na osídlenie v 3. okrese na pravom brehu Wienflussu. Podľa tejto verzie postupne vzniklo z Vedunia pomenovanie Viedinia, z toho v starovekej nemčine Venia, Wenia alebo Wennia a (v stredovekej nemčine) Wienne a tento názov sa zachoval dodnes v hovorovom pomenovaní „Wean". Podľa tejto teórie pomenovanie Vindobona nijak nesúvisí s názvom Viedne. Tomu odporuje druhé vysvetlenie. Podľa neho keltské oppidum (nemecky malé mesto) na Leopoldsbergu sa volalo Vindobona, čo v preklade znamená niečo ako „Biela zem“ alebo "Biely tovar“ a následne prekonalo viacero zmien (Vindovona, Vindovina, Vindomina, Videnica, Vidunji, Viden, Wienne, Wien, po slovensky Viedeň).

Prvá cestná sieť vo Viedni

V 1. storočí nášho letopočtu vznikol v strede dnešného 1.  okresu (Vnútorné mesto) za cisára Trajána rímsky vojenský tábor Vindobona s priľahlým civilným mestom. Hoci mala Viedeň omnoho menšiu rozlohu, Dunaj bol k dnešnej mestskej oblasti omnoho bližšie. Ulica Porzellangasse, ktorá sa nachádza v dnešnom 9. okrese bola v tom čase napríklad ramenom Dunaja, ulica Liechtensteinstrasse nábrežím Dunaja a ulica Salzgries v 1.  okrese slúžila ako prístavisko lodí. Pozostatky kúpeľov s kúrením typu hypokaustum z tejto doby je možné obdivovať v „rímskych ruinách“ pod Hoher Markt. Aj prvá plánovane založená a budovaná cestná sieť v oblasti Viedne je dielom Rimanov. Viacero hlavných ulíc dnešnej dopravnej siete má svoj pôvod práve tam. Vindobona nadobudla plánovaným napojením na cesty na dôležitosti a získala v roku 212 mestské práva (municípium). Následkami sťahovania národov a s ním spojeného veľkého požiaru okolo roku 400 však mesto utrpelo vážne škody. Následne sa rímski osídlenci stiahli z Vindobony. Medzi 5. a 8. storočím tu preukázateľne zostal iba zvyšok osídlenia medzi Hoher Markt a St. Ruprecht. 

V 7. storočí prichádzali do oblasti Viedne Slovania a Avari. Rímsky vojenský tábor Vindobona sa s konečnou platnosťou stala minulosťou. V roku 881 sa osídlenie prvýkrát označilo názvom Venia (resp. Weniam).