Beč je u keltsko-rimskom periodu nosio naziv Vindobona prema keltskom nazivu Vedunia (nemački: Waldbach, srpski: šumski potok). Sa rečju vino (nemački: Wein) naziv grada Beča (nemački: Wien) zapravo nema ništa zajednčko. Nakon što su Rimljani u 5. veku napustili oblast Beča, mesto na kome se danas nalazi Beč spominje se kao Vindomina i Venia, a nakon 1000. godine i kao Viennis i Wienne.

Doseljavanje i izgradnja naselja na prostoru današnjeg Beča, glavnog grada Austrije, a istovremeno i pokrajine, počelo je od 5000. godine pre n.e. u mlađem kamenom dobu. Primer prvog doseljavanja je današnja oblast Antonshöhe u 23. bečkoj opštini, u šumskoj oblasti Maurer Wald koja je pod zaštitom države kao prirodni rezervat. Podunavska kultura se deli u dve glavne grupe, zapadnu i istočnu. Međutim, interesantna je činjenica da su u današnjem Beču nađeni ostaci iz obe grupe, između ostalih u krajevima Ober Sankt Fajt (Ober St. Veit) u 14. bečkoj opštini i kod parka Verthajmštajn (Wertheimstein) u 19. bečkoj opštini. Dakle, i pre nego sto je postojao grad, prostor Beča bio je kapija koja je povezivala Istok i Zapad.

Iz 1800. godine pre n.e. potiču dokazi o takozvanim „ljudima sa zvonastim peharima“ („Glockenbecherleute“) u oblasti Beča koji su ovo ime dobili po tipičnom obliku keramike sa zaobljenim dnom. Prostor na koji se doseljavaju je gradska terasa koja se i danas još može raspoznati na strmoj padini blizu dela grada koji se naziva Marija am Geštade (Maria am Gestade), kao i kod Ruprehtove crkve (Ruprechtskirche) na Dunavskom kanalu.

Ruprehtova crkva (levo) iz 8. veka je najstarija očuvana crkva u Beču. U njoj se još uvek nalaze vitraži iz 13. veka; Desno: iskopavanja na Trgu Svetog Mihajla otkrila su rimske temelje Beča

Požar u Palati pravde

Sporno je međutim odakle potiče prvobitno ime Beča. Sigurno je samo da je naziv za Beč Wien izveden od keltskog naziva za jedno naselje u procesu koji je trajao više od hiljadu godina. Neki zastupaju verziju da je naziv Wien izveden od reči Vedunia (srpski: šumski potok, nemački: Waldbach) iz keltskog doba La-Téne u 4. veku pre n. e. i smatraju da je to bilo jedno naselje u današnjoj 3. opštini na desnoj obali rečice Vinflus (Wienfluss). Prema njihovoj teoriji, naziv Vedunia najpre je izmenjen u Veidinia, a od ovog je kasnije nastalo staronemačko Venia, Wenia ili Wennia i (srednjenemačko) Wienne, koje se i dan danas održalo u izgovoru dijalekatskog naziva za Beč „Wean“. Po ovoj teoriji, naziv Vindobona nema ništa zajedničko sa nazivom Wien. Ovome međutim protivreči jedno drugo objašnjenje, po kojoj se keltsko naselje na brdu Leopoldsberg zvalo Vindobona, što u prevodu otprilike znači „belo tlo“ ili i „belo imanje“, i taj je naziv nakon toga pretrpeo nekoliko izmena (Vindovona, Vindovina, Vindomina, Videnica, Vidunji, Viden, Wienne, Wien).

Prva ulična mreža u Beču

U 1. veku je u centralnom delu današnje 1. opštine (Inere Štat - Innere Stadt) u vreme vladavine imperatora Trajana nastao rimski vojni logor Vindobona, koji se graničio sa civilnim naseljem. Dok je Beč tada po površini bio mnogo manji nego današnji grad, Dunav je u to vreme bio mnogo bliži današnjem području grada. Tako je ulica Porcelangase (Porzellangasse), danas u 9. opštini, u tom periodu bila rukavac, današnja Lihtenštajnštrase (Liechtensteinstraße) je bila ulica na adi uz obalu, a Zalcgris (Salzgries) u 1. opštini služila je kao pristajalište za brodove. Ostaci jednog kupališta sa podnim grejanjem (hipokaust) iz ovog perioda mogu se obići u Rimskim ruinama (Römische Ruinen) ispod Visoke tržnice (Hoher Markt). Rimljani su zaslužni i za prvu plansku izgradnju ulica na prostoru Beča. Nemali broj glavnih ulica današnje saobraćajne mreže potiče iz tog doba. Naselje Vindobona je planskim otvaranjem sve više dobijalo na značaju i 212. godine dobija gradsko pravo (municipium). Posledice seobe stanovništva i s tim u vezi veliki požar oko 400. godineteško su pogodili grad. Nakon toga su rimski doseljenici povučeni iz Vindobone, a između 5. i 8. veka ostali su samo ostaci naselja između današnjeg Hoher Markta i Sankt Ruprechta.

U 7. veku je sve više Slovena i Avara prodiralo na prostor današnjeg Beča. Rimski vojni logor Vindobona je konačno pripadala prošlosti. 881. godine se prvi put nailazi na naziv Venia (odnosno Weniam) za Beč.