V počátcích českého státu stál kníže Vratislav II. jako věrný spojenec při římském králi Jindřichu IV. v jeho bojích proti papeži Řehořovi VII. o investituru (uvádění kněží do úřadů) a pomohl mu vybojovat řadu bitev. Během bojů mezi Jindřichem IV. a jeho protivníky Leopold II. Krásný, panovník říšské východní marky (dnešní Rakousko), usoudil, že je na čase napadnout oslabené české knížectví, konkrétně sousední Moravu.
Proto Vratislavův bratr, moravský Přemyslovec kníže Konrád I. Brněnský, vpadl s vojskem na Leopoldovo území. O následné bitvě u Mailberku 12. května 1082 se zachovaly zprávy jako o jedné z nejurputnějších a nejkrvavějších té doby, i když skutečné počty bojovníků a ztráty nikde nebyly zaznamenány.
Podle Kosmovy kroniky české se Leopold snažil dodat odvahu svému vojsku těmito slovy: „Bojovníci, jejichž síly jsem já sdostatek zkusil v mnoha šťastných bitvách, nebojte se těch prchavých stínů, jimž jest – a já toho velmi lituji – otevřeno pole k útěku. Vím totiž, že se neodvažují dáti s vámi do boje. Což nevidíte, jak prozrazují svoji slabost tím, že je strach sehnal do jedné hromady? Není tam viděti zbraně v žádné podobě, ovce jsou to, myslím si, a žrádlo vlků.“
Tato plamenná řeč však nepomohla. Češi a Moravané pod vedením knížat Konráda I. a jeho bratra Oty Sličného zabili mnoho nepřátel a slavili velké vítězství, i když za cenu vlastních značných ztrát. Leopold II. Krásný se musel zachránit útěkem, ale české a moravské vojsko jej i jeho muže daleko pronásledovalo, zajalo mnoho Leopoldových bojovníků a získalo velké množství kořisti.
Přes toto jasné vítězství Vratislav II. zřejmě realisticky vyhodnotil situaci a nepokusil se rakouské země fakticky začlenit do své říše, i když mu byly uděleny jako právoplatné léno. Zřejmě by je nebyl schopen udržet. Neplýtval tedy silami tady a dále se orientoval na dvůr římského krále Jindřicha IV. Ten mu také za jeho věrné služby o tři roky později, roku 1085, udělil titul českého krále. Vratislav II. se tak stal prvním králem v našich dějinách.
