För att kunna vinna befrielsekriget hade Gustav Vasa varit tvungen att låna stora summor från Lübeck. Efter krigsslutet uppgick skulden till sammanlagt 120 000 lybska mark. Under 1520-talet och början av 1530-talet var avbetalningen av den lybska skulden en återkommande fråga som ständigt användes för att motivera nya skatter. Inte alla skattepengar som drogs in användes dock för att betala av skulden. För den var i själva verket inte så betungande som Gustav Vasa försökte göra gällande. Den var däremot var en utmärkt förevändning för att samla in skatter som sedan användes för att bekosta kungens militära utgifter. Men skulden var trots allt något som vållade Gustav Vasa bekymmer och han såg tidigt den rika kyrkan som en möjlig lösning på problemet. Redan det första året av Gustav Vasas regering hade kyrkan mer eller mindre tvingats att låna ut 43 000 mark till kungen så att han kunde göra en första avbetalning. Ännu ett intrång på kyrkans frihet skedde 1524 när Linköpings stift tvingades att stå för halva kostnaden av krigståget på Gotland. Argumenteringen för detta var också tydligt påverkad av Luthers tankar. Snart skulle Gustav Vasa med hjälp av de lutherska idéer som spreds från Tyskland smida planer på att konfiskera all kyrklig egendom.

De lutherska idéerna kom till Sverige huvudsakligen med tyska legoknektar och svenskar som hade studerat vid de tyska universiteten. En av dessa studenter var Olaus Petri som skulle bli en av reformationens förgrundsgestalter tillsammans med den äldre Laurentius Andreæ som i egenskap av ärkediakon i Strängnäs var hans överordnade och som Olaus lyckades övertyga om hållbarheten i de lutherska idéerna. Den främste motståndaren mot reformationen i Sverige var Hans Brask som var biskop i Linköping. Han ville redan 1523 döma Olaus Petri som kättare men Gustav Vasa avstyrde processen. Strax efter kungavalet 1523 hade nämligen Laurentius Petri blivit kungens kansler och därmed blivit Gustav Vasas närmaste man och under hela 1520-talet skulle Gustav Vasa skydda dem som kritiserade den katolska kyrkan. Vi har dock ingen som helst kunskap om hur Gustav Vasas personliga religiositet yttrade sig. Det förefaller inte heller som han var nämnvärt intresserad av teologi utöver de möjligheter som reformationen erbjöd honom att stärka sin makt.

Gustav Trolle hade blivit avsatt som ärkebiskop i Uppsala 1517 av Sten Sture den yngre och bortsett från hans korta återkomst under Kristian II hade den svenska kyrkan saknat en fungerande ledare. Trots att påven ännu inte erkänt avsättningen av Gustav Trolle valde ett enhälligt domkapitel i Uppsala Stureanhängaren Knut Mickelsson till ny ärkebiskop 1523. Gustav Vasa ogillade dock valet och erbjöd istället posten till Johannes Magnus som just hade kommit till Sverige som påvlig legat med uppdrag att bekämpa det lutherska kätteriet. Johannes Magnus accepterade oklokt nog erbjudandet och blev därmed helt beroende av kungen eftersom han saknade stöd både i sitt eget domkapitel och hos påven. Med den nye ärkebiskopen i Gustav Vasas händer blev det som sagt Hans Brask som fick ta ledningen i kampen mot reformationen. Till sin hjälp i detta arbete grundade han 1523 Sveriges första pappersbruk i Linköping och ett tryckeri i Söderköping från vilket kritiska skrifter mot Luther spreds. I Stockholm grundades 1526 ett kungligt tryckeri som spred lutherska skrifter och Gustav Vasa beordrade samma år att det rivaliserande tryckeriet i Söderköping skulle läggas ned. 1526 trycktes också en svensk översättning av det Nya testamentet. Olaus Petri hade året innan trotsat den katolska kyrkans krav på celibat för präster genom att gifta sig i storkyrkan i Stockholm och även brutit mot kyrkans lag genom att hålla predikningar på modersmålet.

Ett viktigt budskap i de lutherska skrifterna var att kyrkan inte ägdes av prästerna utan av folket i församlingen. Därmed ansågs det vara helt riktigt att man kunde ta kyrkans egendom i anspråk för att bekosta statliga utgifter, som till exempel skulder till Lübeck. Att Gustav Vasa inte hade någon större respekt för äganderätten visade han upprepade gånger prov på som kung när han på ett mycket maktfullkomligt sätt konfiskerade egendomar för personlig vinning med hänvisning till svaga arvsanspråk. Ett flagrant exempel på detta skedde 1526 när han upphävde en donation av Gripsholm som Sten Sture den äldre hade gjort till Kartusianklostret i Mariefred. Gustav Vasa ansåg att han hade större rätt till Gripsholm eftersom det var en gammal släktgård och att han var barnbarn till Sten Stures syster. Klosterbröderna kördes därför omgående iväg utan något juridiskt krångel. Tilltaget var ett klart fall av maktmissbruk och dessutom onödigt eftersom Gustav Vasa skulle få kontroll över all kyrklig egendom året efter genom det beslut som togs av riksdagen i Västerås.

Det stora genombrottet för reformationen kom nämligen med Västerås riksdag i juni 1527. Detta riksmöte inleddes med att kungen klagade över rikets dåliga ekonomi och jämförde kronans och folkets svaghet med kyrkans väldiga rikedom. Gustav Vasa hotade rent av med att avgå ifall ingen förbättring skedde. Följaktligen beslutade riksdagen att alla donationer som hade gått till kyrkan sedan "kung Karls tid" skulle återbördas till de rätta arvingarna samt att kyrkans slott och överflödiga intäkter skulle gå till kronan. Även om riksdagen hade avslöjat att det fanns ett starkt konservativt stöd för den katolska kyrkan bland allmogen, vilket även det pågående upproret i Dalarna visade, var kyrkans makt nu bruten. I strid mot landslagens bestämmelser blev biskoparna hädanefter inte kallade till riksrådets möten. Ärkebiskop Johann Magnus befann sig på diplomatiskt uppdrag i Polen och valde att inte återvända till Sverige när han fick höra om beslutet i Västerås. Även Hans Brask fann det för gott att lämna landet. Inför sin länge väntade kröning den 12 januari 1528 lät Gustav Vasa biskopen i Strängnäs viga tre andra biskopar till sina ämbeten trots att detta var något som skulle utföras av påven. Den ed som kungen skulle svära vid kröningen ändrades också så att han inte skulle behöva värna kyrkans privilegier. Den formella brytningen med katolicismen kom slutligen 1531 när en lutheran (Laurentius Petri) utsågs till ny ärkebiskop istället för den landsflyktige Johannes Magnus och en luthersk mässordning skriven av Olaus Petri utfärdades, den blev sedan obligatorisk 1536.

Gustav Vasa hade under årens gång krävt ut så många skatter med hänvisning till den lybska skulden att de skulle ha räckt till att betala denna flera gånger om. Men med indragningen av kyrkans jord var kronan så rik att det var svårt att försvara nya skatter till avbetalningar till skulden. Fast Gustav Vasa gjorde det iallafall när han krävde en skatt bestående av socknarnas kyrkklockor 1531, vilket utlöste det tredje dalupproret. En reglering av den lybska skulden hade dock ägt rum redan 1529 och den hade förhandlats fram av Gustav Vasas svåger Johan av Hoya samt sekreteraren Wulf Gyler som skötte Sveriges utrikespolitik. Fast Lübecks omfattande handelsprivilegier var ett problem för Gustav Vasa och i takt med att hans ställning i och utanför Sverige blev allt starkare började han att föra en utmanande politik mot Lübeck. Han anklagade Lübeck för att ha lurat hans förhandlare och att Sverige i själva verket hade betalat för mycket samt knöt kontakter med deras holländska rivaler. När krig bröt ut mellan holländarna och Lübeck 1533 erbjöd Gustav Vasa militär hjälp till Lübeck i utbyte mot en begränsning av deras privilegier. Lübeck tackade nej och Gustav Vasa svarade med att riva upp avtalet från 1529 samt egenmäktigt lägga beslag på Lübecks egendomar i Sverige. Johan av Hoya som hade ställt sig som personlig garant för avtalet bestämde sig för att till kungens stora vrede överlämna sig till Lübeck. Denna vrede drabbade även hans medförhandlare Wulf Gyler som skrämd av hot om avrättning flydde landet 1534.

Den slutliga uppgörelsen med Lübeck kom under grevefejden 1534-1536. Detta var ett danskt inbördeskrig där Lübeck stödde ett uppror som ville återinsätta Kristian II på tronen, vilket var helt oacceptabelt för Gustav Vasa som därför intervenerade i kriget. Ytterligare brännvätska var Lübecks försök att övertala Sten Stures ende kvarvarande son Svante att göra uppror mot Gustav Vasa. En svensk styrka invaderade Halland och intog Halmstad samt inledde en belägring av Varberg. Upprorshären som leddes av Johan av Hoya misslyckas med att ta tillbaka Halmstad och i januari 1535 blev hans armé besegrad varefter svenskarna intog Helsingborg. Under sommaren besegrades den lybska flottan i flera slag av den allierade dansk-svensk-preussiska flottan. Den danske kungen Kristian III lyckades vid samma tid återerövra nästan alla de delar av Danmark som anhängarna till hans farbror med samma namn höll. Våren 1536 föll Malmö till svenska styrkor och Köpenhamn kapitulerade till Kristian III den 28 juli. Därmed var kriget i praktiken över och Lübeck tvingades i stilleståndet den 29 augusti att acceptera indragningen av dess handelsprivilegier samt erkänna att Sveriges skuld var betald.

I slutskedet av Grevefejden hade en konspiration bland Stockholms borgare mot Gustav Vasa avslöjats som han kunde utnyttja till att stärka sin makt över huvudstaden. Dessutom hade missnöje med skatter lett till att stora bondeoroligheter i Dalarna utbrutit vid samma tid och kostat flera fogdar och knektar livet. En av fogdedräparna var en krononybyggare från Värend vid namn Nils Dacke. Efter att oroligheterna hade lugnat ner sig sommaren 1536 beordrade Gustav Vasa sina män att hålla räfst med bondemenigheterna det följande året och bestraffa de upproriska smålänningarna med böter och avrättningar

Gustav Vasa ställning kunde nu inte vara starkare och de följande åren såg en uppgörelse med de ledande reformatorerna Laurentius Andreae och Olaus Petri. Dessa två hade hela tiden propagerat för en fri folkkyrka medan kungen önskade sig en statskyrka som var helt under hans kontroll. När reformationen var ett faktum blev denna motsättning allt mer tydlig och de två reformatorerna avlägsnades från kungens kansli 1531 respektive 1533. I deras ställe kom Kristoffer Andersson som snarast förespråkade en reformkatolsk linje och som misstroddes av Gustav Vasa till den grad att han gick i landsflykt och dömdes till döden i sin frånvaro. En annan tidig lutheran knuten till kungens kansli var Olof Bröms som blev så illa behandlad av kungen att även han gick i landsflykt 1537. Ett tydligt mönster framträder i den höga personalomsättningen i det kungliga kansliet och smädeskrifterna från de många landsflyktiga före detta medarbetare till Gustav Vasa. Kungen var sjukligt misstänksam, oärlig och våldsam mot sina underlydande.

Under inflytande från sina tyska rådgivare beslutade Gustav Vasa 1539 att kyrkan skulle underordnas en superintendent som var utnämnd av kungen. Konsekvenserna av reformen var att kyrkans självständighet försvann och att konflikten med de gamla reformatorerna som ville ha en oberoende folkkyrka åter kom upp till ytan. Gustav Vasa visade dock vem det var som bestämde och fick Laurentius Andreæ och Olaus Petri året efter dömda till döden för förräderi, domarna blev dock omgående omvandlade till skyhöga böter istället. Men år 1541 inträdde dock en viktig milstolpe i både reformationens och Sveriges historia som både kung och reformatorer gladde sig åt. Det var då den av Olaus Petri redigerade översättningen av bibeln fullbordades, vilken fick ett stort inflytande på det svenska språkets utveckling.