Nyheten om Gustav Vasas uppviglingsförsök i Dalarna nådde Kristian II i Vadstena där han firade julen under ett uppehåll på sin eriksgata. Ett mer akut problem var dock det oroliga läget i Småland och inte minst de stora svårigheterna med att finansiera lönerna till de legoknektar som han hade använt för att erövra Sverige. Det var pengabristen som tvingade honom att avbryta sin eriksgata och återvända till Köpenhamn varifrån han sedan reste till sin svåger kejsar Karl V i Nederländerna för att få till stånd nya lån. Innan han lämnade svenskt territorium hann han dock med att avrätta munkarna i Nydala kloster som beskylldes för att stödja det småländska upproret. Styret av Sverige sköttes i kungens frånvaro av riksrådet som dominerades av fyra biskopar, de två svenskarna ärkebiskop Gustav Trolle och biskop Otto i Västerås samt två danskar som efterträtt personer som avrättades i Stockholms blodbad. Dessa var Didrik Slagheck som var biskop i Skara och hövitsman i Stockholm samt Jens Beldenek som var biskop i både Odense och Strängnäs. Utöver dessa hade nästan samtliga slott anförtrotts danska och tyska fogdar.

Gustav Vasa hade valts till hövitsman av allmogen i Siljansbygden i januari och mars vann han över hela Dalarna på sin sida. Men det var först i april som stridigheterna började när Gustavs folk lyckas ta sig över Dalälven vid Brunnbäcks färja och driva bort de kungliga trupperna. Den första riktigt stora framgången var en drabbning utanför Västerås som ledde till att staden (men inte slottet) erövrades. Med undantag av slotten kontrollerade Gustav i början av maj Dalarna, Västmanland, Närke samt hela Norrland och ryckte fram i Uppland där Uppsala intogs den 19 maj. Till detta ska även läggas till Småland som hade befriat sig på egen hand samt Västergötland och Värmland där kungens ställning hotades av omfattande missnöje bland bönderna som hade mördat flera av hans fogdar. Kristian II hade dessutom fortfarande finansiella problem och hade varit tvungen att avdanka stora delar av sin här trots att han höll på att tappa greppet om Sverige. Riksrådet försökte därför lösa den svåra situationen med förhandlingar och lät fängsla den stridbare Didrik Slagheck samt utnämna Gustav Trolle till rikshövitsman. Trolle lovade Gustav Vasa fri lejd, amnesti och säte i riksrådet ifall han kom till Stockholm och slöt fred. Gustav Vasas mor och moster hade även tvingats att skriva brev som uppmanade honom att sluta fred. Men Gustav Vasa var alltför misstänksam och framgångsrik för att ta intryck av dessa fredstrevare.

Upproret mot Kristian II fortsatte att öka i styrka och vid ett landsting i Skara den 2 juni uppsade Västergötlands bönder och frälse sin trohet och lydnad till kungen och anslöt sig till upproret. Den 25 juli slöt biskopen i Linköping, den kände Hans Brask, ett avtal med Gustav Vasa som innebar att även Östergötland anslöt sig till upproret, fast dess högfrälset förblev i likhet med kollegorna i Uppland och Södermanland trogna till kungen. Befrielsekriget mot Kristian II blev sedan slutgiltigt organiserat under Gustav Vasas ledning vid ett herremöte i Vadstena då han den 23 augusti valdes till riksföreståndare. Efter valet ökade avhoppen från frälset och de som inte var villiga att svika kungen började fly till Danmark, bland dem ärkebiskop Gustav Trolle. Endast slotten och Finland kontrollerades därefter av Kristians män. Men Nyköpings slott kapitulerade under senhösten, Stegeborgs slott strax före jul, Örebro slott strax efter nyåret 1522 och Västerås slott i januari.

Stegeborgs slotts kapitulation fick också konsekvensen att dess befälhavare Berend von Melen bytte sida och blev en av Gustav Vasas närmaste män. Gustav Vasa själv var inte mycket av en krigare utan både under befrielsekriget och alla följande militära insatser höll han sig mest i bakgrunden och överlät den direkta ledningen åt underlydande. Under resten av befrielsekriget var det de facto Berend von Melen som ledde den svenska krigsinsatsen. För att kunna inta de slott som fortfarande var i danska händer var det dock nödvändigt att ha örlogsfartyg och tungt artilleri. En av Berend von Melens första uppgifter i Gustav Vasas tjänst var därför att med hjälp av sitt goda rykte medverka till det avtal som slöts med Lübeck under våren 1522. I utbyte mot löften om tullfrihet för Lübeck fick den svenske riksföreståndaren allt den militär hjälp som behövdes för att fortsätta kampen mot Kristian II. En 13 skepp stark örlogsflotta köpt på kredit från Lübeck anlände till Söderköping den 7 juni, vilket kan sägas vara den svenska flottans födelsedag. Med hjälp av denna flotta kunde Gustav Vasa förhindra danskarna från att förse slotten med förnödenheter och även gå till offensiven genom att till exempel bränna Hammershus på Bornholm.

Medan belägringarna av de viktiga slotten pågick förbereddes ett fälttåg för att erövra Skåneland som Sverige hade gjort anspråk på alltsedan 1300-talet. Lübeck förklarade krig mot Danmark i augusti och en svensk-lybsk styrka under Berend von Melens ledning samlades i Markaryd i januari 1523. Men den milda vintern med stora översvämningar samt de gränsfreder som bönderna hade slutit förhindrade en framryckning in i Skåne och till slut fick von Melen nöja sig med att ockupera Blekinge. Gustav Vasa ville följa upp denna framgång genom att beordra erövringen av Halland och Bohuslän. Svenska styrkor intog också norra Bohuslän utan några svårigheter och gjorde ett försök att tåga mot Oslo. Gustav Vasas förhoppning om ett nytt anfall mot Skåne släcktes dock när Berend von Melen i strid mot svenska intressen slöt ett stillestånd med Skånes adel i slutet av april. Vid samma tid hade det nämligen skett stora omvälvningar i Danmark. I januari hade ett uppror brutit ut bland den jylländska adeln under kungens farbror hertig Fredriks ledning. I mars hade upprorsmännen valt hertig Fredrik till ny dansk kung och Kristian II gick i landsflykt. Eftersom även den nye danske kungen Fredrik I lovade tullfrihet åt Lübeck låg det inte i deras intresse att stödja den svenska invasionen av Skåne och det var därför som Berend von Melen slöt stilleståndet.

Avsättningen av Kristian II i Danmark innebar att det svenska befrielsekriget hade nått ett viktigt vägval. Skulle Sverige erkänna den nye danske kungen och återupprätta Kalmarunionen eller skulle de utse en annan person till kung och därmed permanent upplösa unionen. I det rådande läget fanns det bara ett tänkbart namn som kunde utgöra ett alternativ till Fredrik I som kung och det var riksföreståndaren Gustav Eriksson (Vasa). Sten Sture den yngre hade visserligen två söner men de var alldeles för unga och Sturepartiet var för alltför svagt efter Kristian II:s utrensningar. Det faktum att båda två dessutom befann sig i fängsligt förvar i Danmark gjorde också att vägen var helt öppen för Gustav Vasas kungaval. Det gällde dock att skynda på innan stämningarna mot unionen hann vända eller ifall Sten Stures söner skulle bli frisläppta och Sturepartiet återfå sin styrka.

Ett hastigt sammankallat herremöte eller riksdag samlades i Strängnäs i juni för att fylla vakanta platser i riksrådet som hade decimerats kraftigt under de senaste årens omvälvningar. Ett av de nyvalda riksråden var Berend von Melen, detta trots att landslagen uttryckligen förbjöd utlänningar att bli riksråd. Ett nyligen anlänt besked från Danmark om att Fredrik I gjorde anspråk på den svenska tronen togs sedan som förevändning att förrätta ett kungaval. Sändebud från Lübeck som stödde Gustav Vasas kandidatur satte press på deltagarna genom att ställa krav på förhandlingar om handelsprivilegier och avbetalningar på de lån som Lübeck hade beviljat Sverige. Om Lübeck inte fick som de ville kunde den nära förestående erövringen av Stockholm spolieras. Föga överraskande blev Gustav Vasa vald till kung den 6 juni och fyra dagar senare beviljades Lübeck omfattande handelsprivilegier som gav dem fullständig tullfrihet i hela Sverige. Detta satte sedan fart på förhandlingarna med Stockholms slotts besättning, Lübeck hade förhalat dem i väntan på att privilegierna skulle godkännas. Den 17 juni kapitulerade Stockholms slott och Gustav Vasa gjorde sitt bejublade intåg i staden på midsommarafton.

Vid samma tid intogs även Kalmar slott och Älvsborgs slott övergavs och brändes ner av danskarna. I augusti landsteg en svensk styrka i Finland och den 10 oktober kapitulerade de sista motståndsfickorna i Olofsborg och Viborg. Därmed var det så kallade Befrielsekriget i princip över. Svenska trupper ockuperade dock fortfarande Blekinge och norra Bohuslän samt gjorde anspråk på Gotland och hela Skåneland medan den dansk-norske kungen Fredrik I fortfarande ville återupprätta Kalmarunionen. Formell fred slöts i Malmö recess den 1 september 1524 varmed de båda kungarna lovade att bevara freden och bli goda grannar. Gustav Vasa gav motvilligt upp anspråken på Skåneland och utrymde Blekinge samt drog tillbaka en styrka i Gotland som hade belägrat Visborgs slott samtidigt som förhandlingarna i Malmö hade pågått. Kungarna enades om att den svåra frågan om Gotlands nationstillhörighet skulle avgöras vid ett senare tillfälle av skiljedomare från ett antal hansestäder, under tiden skulle norra Bohuslän förbli ockuperat av svenska trupper. Skiljedomen kom dock aldrig till stånd och norra Bohuslän lämnades tillbaka 1532 i utbyte mot att Danmark löste in en svensk skuldväxel på 1 200 Rhenska gyllen i Lübeck. Befrielsekrigets huvudmål hade dock uppnåtts med recessen i Malmö, Sverige hade fördrivit tyrannen Kristian II samt upplöst Kalmarunionen och Gustav Vasa var Sveriges oomstridde kung.