Vraťme se ke křížové výpravě, která se odehrála roku 1254. Přemysl se chtěl výpravy zúčastnit a tím podat papeži důkaz křesťanské horlivosti. Po výpravě ale papež stále neučinil nic významného pro legitimování dětí Přemysla s Anežkou. K tomu došlo až o mnoho let později. Výprava trvala rok, s žádným výraznějším odporem se rytíři nesetkali. Prusové se většinou podrobili a přijali křest. Přemysl nechal v Královci položit základní kámen.
V roce 1257 začíná konflikt, neboť se Přemysl nechtěl smířit se ztrátou moci nad štýrským vévodstvím. Věděl, že mír, který kdysi uzavřel s uherským králem, nebude trvat věčně. Zaútočil tedy na Bavorsko. Nejdříve se mohlo zdát, že jde jen o okrajovou válku. Přemysl chtěl přepadem vyřešit starší spor s Jindřichem Dolnobavorským, knížetem a zároveň zetěm uherského Bély IV. Byl si jistý vítězstvím, ale početná a zkušená armáda Jindřicha Přemysla zaskočila a zahnala. Došlo k velkému selhání, jelikož při úprku se mnoho těžkooděnců utopilo v řece, do které spadli díky prolomení mostu. Přemysl musel odevzdat Sušicko, měl na něj nárok Jindřich. Válka s Bavory se nevyvedla a navíc se dostavil další problém. Jelikož byl Jindřich příbuzný s Bélou, pomsta z uherské strany na sebe nenechala dlouho čekat.
Vše začalo vpádem Uhrů do Korutan. Zdejšímu vládci, Oldřichu Sponheimskému, neváhal Přemysl pomoci. Na začátku roku 1259 české vojsko zamířilo za podpory tamní šlechty do Štýrska, odkud vyhnalo Uhry. Tím se dostalo babenberské dědictví opět do rukou Přemysla. Uherský protivník si to nenechává líbit. V zimě se vydávají dvě mohutné armády proti sobě. Naštěstí oběma stranám došlo, že toto ročním období není k boji vůbec vhodné, a tak se rozhodli sjednat rytířské příměří. Bylo dohodnuto, že se bitva uskuteční do 24. června. Soupeřící strany si tedy mohly zajistit větší vojska a přivést spojence na pomoc. A také se tak stalo – koncem června proti sobě nedaleko Kressenbrunnu stály obrovské armády. Nepřátelská vojska stála na obou březích řeky Moravy. Téměř čtrnáct dní se čekalo na to, kdo učiní první krok přes řeku. Přemysl poté navrhl řešení, které spočívalo v tom, že jedna armáda ustoupí, zatímco ta druhá se v klidu přebrodí. Béla nabídku přijal a začalo se bojovat na české straně. 12. července se stala zvláštní věc, Uhři tvrdili, že Češi nedodrželi úmluvu a Češi naopak tvrdili, že Uhři začali hned při pochodu obkličovat české postavení. Začal krutý boj, při kterém se řeka Morava proměnila v masový hrob. Česká armáda se vydala pronásledovat nepřítele a hnala ho až k Prešpurku. Český král měl údajně možnost obsadit i královský trůn poraženého souseda, ale neudělal tak, neboť správně tušil, jaký chaos by změnou hranic v Evropě nastal. Přemysl v bitvě zvítězil a získal zpátky Štýrsko.
Po vítězství v Kressenbrunnu v roce 1260 začalo pro Přemysla nejvlivnější desetiletí jeho vlády. Dařilo se mu ve všem, nač sáhl. Ovládal veliké území, jeho stát změnil výrazně hranice a získaným Rakouskem a Štýrskem se protáhl na jih. Přemysl ovládal evropskou velmoc. Jediným problémem byly Uhry. Bélův syn, Štěpán, se stále nesmířil se ztrátou Štýrska a dělal problémy při mírových jednáních. Přemysl vyčkával a v hlavě se mu začal rýsovat plán. Aby se spojil s Uherskem, musel by vstoupit do nového sňatku, což by mu ale problém nečinilo. Markéta, která při jeho boku stála osm let, trpěla tím, že jí Přemysl nikdy nemiloval, a obviňovala se za to, že mu nikdy neporodila legitimního potomka. Po bitvě v Kressenbrunnu se říšské listiny, které byly důvodem sňatku těchto dvou, staly nepodstatnými. Po uherském tažení v srpnu 1260 se Přemysl vrátil do Prahy. Znovu se obrátil na papeže, aby uznal jeho tři levobočky legitimními. Ten tentokrát svolil. Tím Přemysl elegantním způsobem pomalu vykličkoval ze sňatku. Poté přikázal biskupovi, aby je s Markétou rozvedl. V dubnu 1261 uzavřel s Bélou „věrné spojenectví“, jehož symbolickým výrazem měl být sňatek s Bélovou vnučkou. Markéta, kterou odstrčil, v Českém Krumlově v roce 1267 umírá. Přemysl se pokusil dodržet alespoň týdenní smutek, ale už 25. října si v Prešpurku bere uherskou princeznu Kunhutu. Ta byla prý neuvěřitelně krásná. Po čtvrt roce oba novomanželé přijali korunovační klenoty od arcibiskupa Wernera von Eppensteina. Korunovace byla vydařenou akcí, oslavy v Praze byly velkolepé a Přemysl byl na vrcholu všeho – moci, štěstí a v neposlední řadě slávy.
V roce 1262 Přemysl pomohl podpořit Richarda Cornwallského, anglického vzdorkrále římskoněmecké říše. Zastal se ho a Richard se Přemyslovi rozhodl odvděčit. Propůjčil mu v léno Rakousko a Štýrsko. To Přemyslovi pomohlo, neboť držení alpských zemí v jeho rukách dostalo i nějaký právní základ. V té době se na scéně totiž objevuje Friedrich Bádavský, což byl syn Markétiny sestry Gertrudy a i on si dělal na tato území nárok. Nestihl však ani bojovat, ani vyjednávat, jelikož byl při tažení do Itálie v roce 1268 se svým přítelem Konradem Štaufským popraven v Neapoli. Zlí jazykové tvrdí, že hrdelnímu rozsudku napomohl Přemysl. Neví se to jistě, dá se však říci, že tato událost Přemyslovi usnadnila zbavit se nepřítele.
V roce 1265 se českému králi narodila holčička, která byla pojmenována po matce. Přemysl se rozhodl vyžádat si privilegium od Richarda o tom, že dědičkou může být i malá Kunhuta. V tom samém roce se Přemysl od Richarda dočkal další přízně, byl jmenován obráncem říšských statků a práv na celém území sahajícímu až k pravému břehu řeky Rýna. Přemyslovi se tím naskytla možnost obsadit Chebsko, a v roce tak i činí. K českému státu Chebsko připojil pod záminkou, že se jedná o dědictví po matce. Král byl šťasten, že se mu tak vede a chtěl uskutečnit ještě několik křížových výprav do pohanských zemí. Jeho sny se v roce 1267 proměnily ve skutečnost, nedošel ale s armádou daleko, počasí mu nepřálo a hlavním důvodem zrušení výpravy byl zákaz samotného papeže. Ten se nejspíše zalekl velkých ambicí, které český král měl.
Díky narůstající slávě Přemysl opomenul řešit stále častější nepokoje ve svém impériu. To drželo pohromadě jen silou vůle panovníka.
V Poděbradech roku 1268 byla králi nabídnuta smlouva se svým přítelem, vévodou Oldřichem Sponheimským z Korutan. Vévoda, který neměl žádné děti, tudíž žádného případného dědice pro jistotu vévodství chtěl vévodství přenechat Přemyslovi. Oldřich měl sice bratra, se kterým ale vedl letitý spor a tato smlouva měla být jakousi pomstou. Přemysl tedy svolil a smlouvu podepsal. Oldřich opravdu zanedlouho zemřel a díky poděbradské smlouvě se český král v roce 1269 stává vévodou Korutan. Během let získal i oblasti Kraňska a Furlansko mu připadlo v 70. letech 13. století. Jeho území se tak protáhlo ještě více na jih, téměř k břehům Jaderského moře.