Rzymianie
Teren dzisiejszego Wiednia był zamieszkiwany od tysięcy lat. Wynika to z geograficznego położenia miasta, które leżało na przecięciu starożytnych szlaków handlowych i szlaku bursztynowego z Dunajem. W okresie osadnictwa, na początku epoki brązu i żelaza, wzgórza wznoszące się ponad Wiedniem zajmowało celtyckie plemię Bojów (prawdopodobnie od 500 p.n.e.), ale około 50 p.n.e. zostało wyparte przez Daków, którzy utworzyli na tych terenach królestwo. Nie przetrwało ono jednak długo. Obszar Wiednia został wchłonięty przez sąsiednie celtyckie królestwo Noryków.
W roku 15 p.n.e. Rzymianie pod wodzą cesarza Augusta posunęli się w głąb Norikum, aż do linii Dunaju i przyłączyli te ziemie do rzymskiej prowincji – Panonii. Przez następne cztery stulecia rzeka była wykorzystywana jako naturalna granica militarna (czyli rzymski Limes), dodatkowo wzmocniona licznymi fortami, zbudowanymi na brzegach. Główny rzymski obóz na tym odcinku Dunaju znajdował się w Carnuntum, na wschodzie, razem z Wiedniem – czy Vindoboną, jak go wtedy nazywano – jako podległym fortem.
Uważa się, że rzymskie forum znajdowało się w rejonie Hoher Markt, w dzisiejszym Innere Stadt. W pierwszym wieku n.e. Vindobona stała się bazą dziesiątego legionu, którego zadaniem było odpieranie ataków sąsiednich plemion germańskich na północy i wschodzie, szczególnie Markomanów i Kwadów. Te dwa plemiona przebiły się przez granicę na Dunaju w 169 r. n.e. i zostały odparte przez cesarza Marka Aureliusza, który zmarł przypuszczalnie w Vindobonie w 180 roku n.e.
Babenbergowie
Rzymianie ostatecznie oddali Vindobonę Hunom w 433 roku n.e., a miasto, jak i resztę Europy, pochłonęły mroki średniowiecza. Jednakże nawet na tak wczesnym etapie rozwoju, podczas wielkich wędrówek ludów po upadku rzymskiej potęgi, obszarowi obecnego Wiednia, naciskanemu od wschodu przez Hunów, a następnie przez Awarów, od północy i południa przez Słowian, a od zachodu przez plemiona germańskie, udało się przetrwać w całości.
Koronacja Karola Wielkiego na cesarza Rzymu w roku 800 n.e. wyznaczyła koniec okresu wczesnego średniowiecza w Europie. Niektóre rejony współczesnej Austrii stały się wojskowymi koloniami, określanymi przez XIX-wiecznych historyków terminem Marchii Naddunajskiej frankońskiego imperium Karola Wielkiego. Wraz z upadkiem imperium w 888 roku, ujarzmianie germańskich ziem kontynuował saski król, Otto Wielki. Jego następca, Otto II, przekazał Marchię Wschodnią rodowi Babenbergów w 976 roku, który miał za zadanie obronę wschodnich granic cesarstwa, ponownie utworzonych na Dunaju. Babenbergowie rządzili tym terytorium przez następne 270 lat, początkowo jako margrabiowie, a następnie jako książęta.
W poszukiwaniu daty powstania państwa wielu austriackich naukowców wskazuje na pierwsze pojawienie się nazwy Ostarrichi w łacińskim pergaminie około roku 996. Jednakże w średniowieczu region ten był określany po prostu jako provincia orientalis lub nazywany od imienia pierwszego władcy, margrabiego Leopolda I (976-94). Z początku margrabstwo Babenbergów ograniczało się do małego odcinka Dunaju ze stolicą w Melku, lecz stopniowo rozwijało się na wschód i na północ. Sukcesywnie Babenbergowie zakładali kolejne klasztory w okolicy, a w szczególności Leopold III (1095-1136), który został później kanonizowany za swoje zasługi i stal się świętym patronem kraju.
W 1156 roku za panowania Henryka II Jasomirgotta (1141-77), margrabstwo Babenbergów zostało wreszcie wyniesione do rangi księstwa ze stolicą w Wiedniu i książęcym pałacem w Am Hof. Jednakże wraz ze śmiercią księcia Fryderyka II (1230-1246) na polu bitwy w 1246 roku wygasła męska linia Babenbergów. Spór o panowanie nad Księstwem Austrii i Styrii, bo tak było wówczas nazywane, ciągnął się przez 30 lat. W 1251 roku przyszły król Czech, Ottokar, objął rezydencję w Wiedniu i obwołał się księciem, uzasadniając swoje roszczenie ożenkiem z wdową po Fryderyku II.