Zentrum des frühmittelalterlichen Wien war der Berghof, ein Wirtschaftshof für den Weinbau. Die erste urkundliche Erwähnung im Mittelalter erfolgte 881 in den Salzburger Annalen, wo apud Weniam eine Schlacht gegen die Magyaren stattfand, wobei unklar ist, ob es sich um die Stadt oder um den Wienfluss handelt. Mit dem Sieg des ostfränkischen Königs Otto I. über die Magyaren im Jahr 955 in der Schlacht auf dem Lechfeld begann der Aufstieg Wiens wie auch Österreichs.
Im Jahre 976 wurde unter den Babenbergern die Markgrafschaft Ostarrichi (Marcha orientalis) eingerichtet, auf deren Gebiet, an der Grenze zu Ungarn, auch Wien lag. Bereits im 11. Jahrhundert war Wien ein wichtiger Handelsort, 1155 machte Heinrich Jasomirgott Wien zu seiner Hauptstadt. Nur ein Jahr später wurde Österreich mit dem Privilegium Minus zum Herzogtum erhoben und Wien damit Residenz des Herzogs.
Nach Beendigung des Dritten Kreuzzuges wurde der englische König Richard Löwenherz bei seiner Rückreise nach England von Markgraf Leopold V. dem Tugendreichen 1192 in Erdberg bei Wien (heute im 3. Bezirk) gefangen genommen und in Dürnstein gefangen gehalten.
Mit dem üppigen Lösegeld wurden eine Münzprägestätte eingerichtet und die erste große Stadterweiterung finanziert. 1221 bekam Wien als zweite Stadt im Herzogtum Österreich nach Enns (1212) das Stadt- und Stapelrecht verliehen.[46] Letzteres bedeutete, dass Kaufleute, die durch Wien zogen, in der Stadt ihre Waren zum Verkauf anbieten mussten. Dies ermöglichte den Wienern den Zwischenhandel, sodass Wien bald weit reichende Handelsbeziehungen, insbesondere entlang der Donau und nach
Venedig unterhielt und als eine der bedeutendsten Städte des Reichsgebiets galt.