Vídeň se v dobách Keltů a Římanů nazývala Vindobona, podle keltského označení Vedunia ("lesní potok"). Název Vídeň "Wien" tedy nemá s vínem "Wein" nic společného. Po odchodu Římanů v 5. století se o městu mluví jako o městu Vindomina a Venia,  po roce 1000 nese pak názvy Viennus či Wienne.  

Z osad ve vídeňském prostoru, zakládaných od mladší doby kamenné 5000 př. n. l., například na Antonshöhe v Maurském lese v 23. obvodě, je dnes hlavní město spolkové republiky a zároveň samostatná spolková země: Vídeň. Podunajská kultura se přitom obecně dělila na západní a východní hlavní skupinu. Je zajímavé, že se v současné Vídni vyskytují nálezy obou těchto skupin, mimo jiné v Ober St. Veit (14. obvod) a ve Wertheimsteinském parku (19. obvod). Ještě než vzniklo město, byla tedy Vídeň již vstupní branou mezi Západem a Východem.

Kolem roku 1800 př. n. l. je ve vídeňském prostoru doložen pobyt tzv. „lidí zvoncovitých poharů“, nazývaných podle typického tvaru jejich keramiky se zaobleným dnem. Předpokládá se, že oblastí osídlení byla městská terasa, jejíž pozůstatky jsou dodnes patrné na srázu u kostelu Maria am Gestade a Ruprechtskirche u Dunajského kanálu.

Ruprechtskirche z 8. století (vlevo) je nejstarším vídeňským zachovaným kostelem. V kostele najdeme ještě původní okna ze 13. století. Vpravo: Vykopávky na náměstí Michaelerplatz odhalily části římského opevnění Vídně

Odkud původní jméno Vídně pochází, je ovšem dodnes sporné. Jisté je jen jedno: Jméno „Vídeň“ (Wien) bylo odvozeno během více než jednoho tisíciletí od keltského názvu sídliště. Mnozí zastávají verzi, že se Wien odvíjí od Vedunia („lesní potok“) z keltské doby La Téne ve 4. stol. př. n. l., a odvolávají se na pojmenování sídliště ve 3. obvodě na pravém břehu řeky Vídeňky. Tak se z Vedunia vytvořilo jméno Veidinia a z něho v pozdější starohornoněmčině Venia, Wenia nebo Wennia a (středohornoněmecké) Wienne, jež je prý dodnes zachováno v nářečním „Wean“. Jméno Vindobona podle této teorie s pojmenováním Wien nesouvisí. S tím nesouhlasí další výklad. Podle něj neslo keltské maloměsto na vrchu Leopoldsberg jmeno Vindobona, což v překladu znamená přibližně „Bílá zem“ nebo též „Bílý statek“ a následně prošlo několika proměnami (Vindovona, Vindovina, Vindomina, Videnica, Vidunji, Viden, Wienne, Wien).

První dopravní síť ve Vídni

V prvním století našeho letopočtu vzniklo za císaře Trajána v jádru dnešního prvního obvodu (Vnitřní město, Innere Stadt) římské vojenské opevnění Vindobona s přilehlým civilním městem. Přestože celková plocha Vídně byla tehdy ještě mnohem menší, Dunaj byl dnešnímu území města mnohem blíže. Porzellangasse, dnes ulička v 9. obvodě, byla tak tehdy jedním z ramen Dunaje, Lichtenštejnská ulice ležela na břehu řeky a Salzgries v 1. obvodě sloužil jako přístaviště lodí. Zbytky koupaliště s římským vytápěcím systémem hypokaustum z té doby lze vidět v „Římských ruinách“ pod prostranstvím Hoher Markt.

I první plánovitě založená a vybudovaná síť cest v prostoru Vídně je výtvorem Římanů. Tyto cesty jsou v základech mnoha hlavních silnic dnešní dopravní sítě. Vindobona získávala postupně na významu a v roce 212 obdržela městské právo (municipium). Město bylo kolem roku 400 těžce poškozeno v důsledku stěhování národů a s tím spojeného silného požáru. Římští osadníci byli poté z Vindobony staženi, a mezi 5. a 8. stoletím je doložena jen jedna zbytková osada mezi Hoher Marktem a svatým Ruprechtem.

V sedmém století přibývalo ve vídeňském prostoru Slovanů a Avarů. Římský vojenský tábor Vindobona náležela již definitivně minulosti. V roce 881 byla osada poprvé označena jako Venia (resp. Weniam).