Dunaj se je v keltsko-rimskih časih imenoval Vindobona, ime izvira iz keltskega poimenovanja Vedunia (»Waldbach«). Z vinom poimenovanje Dunaja torej nima povezave. Potem ko so Rimljani v 5. stoletju to območje zapustili, se Dunaj omenja kot Vindomina in Venia, po letu 1000 pa kot Viennis in Wienne.

Iz prvih naselij v dunajskem prostoru, ki so nastajala od mlajše kamene dobe, od 5000 pred našim štetjem naprej, npr. na območju današnjega zaščitenega območja Antonshöhe, na področju Maurer Wald v 23. dunajskem okraju, je do danes nastalo glavno mesto in hkrati samostojna zvezna dežela: Dunaj. Obdonavska kultura se je ob razvoju naselja razdelila na zahodno in vzhodno glavno skupino. Pri tem je zanimivo, da so bili na območju Dunaja, med drugim v 14. okraju Ober St. Veit, in v 19. okraju Wertheimsteinpark, najdeni ostanki obeh skupin. Preden je torej nastalo mesto, je bilo območje Dunaja že stičišče vzhoda in zahoda.

Okoli leta 1800 pred našim štetjem so na območju Dunaja živeli pripadniki t.i. kulture zvončastih čaš, ime so dobili po obliki keramičnih posod z okroglim dnom, ki so jih izdelovali. Kot naselitveni območji sta znani tudi t.i. »Stadtterrasse«, danes znana kot strmina  pri »Maria am Gestade« in cerkev Ruprechtskirche ob kanalu Donave.

Ruprechtova cerkev (levo) iz 8. stoletja je najstarejša ohranjena cerkev na Dunaju. V njej se nahajajo okenska stekla iz 13. stoletja; desno: Izkopanine na Michaelovem trgu so razkrile dele "rimskih temeljev Dunaja"

O izvoru prvotnega imena Dunaja so mnenja še vedno deljena. Gotovo je samo, da je ime Dunaj izpeljano iz keltskega naselbinskega poimenovanja, ki se je oblikovalo v tisočletnem procesu. Nekateri strokovnjaki zastopajo mnenje, da je ime Dunaj nastalo iz imena Vedunia (»Waldbach«) iz keltske latenske kulture v 4. stoletju pred Kristusom. Ime naj bi v tem primeru izhajalo iz poimenovanja naselja v 3. okraju na desnem bregu reke. Po tej inačici se je iz imena Vedunia oblikovalo ime Veidinia, iz tega imena pa kasneje v starovisoki nemščini Venia, Wenia ali Wennia in (v srednjevisoki nemščini) Wienne, to poimenovanje naj bi bilo prisotno še danes v pogovornem jeziku kot »Wean«. Poimenovanje Vindobona po tej inačici nima nobene povezave z današnjim Wien. Temu oporeka druga razlaga, po kateri se je keltska naselbina na območju Leopoldsberg imenovalo Vindobona, kar v prevodu pomeni »bela tla« ali »belo posestvo«, je kasneje prišlo do številnih sprememb tega poimenovanja (Vindovona, Vindovina, Vindomina, Videnica, Vidunji, Viden, Wienne, Wien).

Prvo cestno omrežje na Dunaju

V 1. stoletju našega štetja je na območju današnjega 1. okraja (Innere Stadt) v času vladavine cesarja Trajana nastal rimski tabor Vindobona, na katerega je mejil civilni del mesta. Po površini je bil Dunaj vsekakor veliko manjši, Donava pa je bila veliko bližje današnjim delom mesta. Tako je bila ulica Porzellangasse v današnjem 9. okraju, takrat pritok Donave, ulica Liechtensteinstraße je bila cesta ob bregu reke, Salzgries v 1. okraju pa je služil kot pristanišče za ladje. Ostanki kopališča s kletnimi prostori s pečjo za ogrevanje s toplim zrakom so danes na ogled v »rimskih ruševinah« pod trgom Hoher Markt.

Tudi prvo načrtno zgrajeno cestno omrežje na območju Dunaja je stvaritev Rimljanov. Tudi številne današnje glavne ulice izvirajo iz rimskih časov. Z načrtno dograditvijo je Vindobona pridobila na pomenu, leta 212 je dobila mestne pravice (municipium). Posledice selitve narodov in hud požar okrog leta 400 so močno poškodovali mesto. Zato so se rimski naseljenci umaknili z Dunaja. Med 5. in 8. stoletjem je bil Dunaj samo ostanek naselja med mestnima predeloma Hoher Markt in St. Ruprecht.

V 7. stoletju je bilo na območju Dunaja vedno več Slovanov in Avarov. Rimska Vindobona je nesporno postala preteklost. Leta 881 je bilo naselje prvič poimenovano Venia (oz. Weniam).