Nadal vände 0–2 till 3–2 i set efter nästan 5,5 timmes spel.
Det var Nadals andra seger i Melbourne, den första kom 2009, och nu är han också tidernas främste på herrsidan när det gäller grand slam-titlar. Den första tog han i Franska mästerskapen 2005, och i och med årets seger i Australian Open går han förbi Roger Federer och Novak Djokovic som båda har 20 titlar.
– Det här var en av de mest känslomässiga matcherna i hela min karriär och att få dela den med dig är en ära, säger Nadal till Medvedev.
Nadal har spelat en lång femsetsfinal i Australian Open tidigare. 2012 förlorade han finalen mot Novak Djokovic, Serbien, efter fem timmar och 53 minuter.
– Så jag förstår att du har det tufft nu, säger Nadal, åter igen till sin motståndare.
Satsar vidare
Den 35-årige gruskungen har haft det svårt att lyckas på hardcourt och gräs och hans karriär har också varit kantad av många skador. Den senaste var en fotskada som han fick i samband med Franska mästerskapen i maj, men inte berättade om förrän under hösten när han tvingades till ett nytt skadeuppehåll.
– För 1,5 månad sedan visste jag inte om jag skulle kunna spela någon mer tennis och nu står jag här med den här pokalen. Om ni visste vad jag kämpat för att få den, säger Nadal.
Nadal säger att han inför finalen i Melbourne inte visste om det skulle bli något mer spel i Australian Open.
– Men nu har jag fått energi att spela vidare och jag ska göra mitt bästa för att komma tillbaka.
Andra finalförlusten
Medvedev vann det första setet med 6–2 och då såg det ut som att han skulle kunna gå mot en enkel seger. Men i andra set lyckades den spanske förre världsettan ta setet till tiebreak, som Medvedev ändå vann med 7–5.
I det tredje setet bröt Nadal Medvedevs serve till 5–4 och tog sedan hem setet. Nadal tog sedan hem det fjärde med samma siffror, 6–4.
I det avgörande setet bröt Nadal fram till 3–2, men Medvedev bröt tillbaka till 5–5. Nadal bröt sedan till 6–5 och servade därefter hem matchen efter fem timmar och 24 minuter.
För Medvedev, andraseedad i turneringen, var det andra finalförlusten i rad i Australian Open. I fjol förlorade han mot Novak Djokovic.
– Vilket osannolikt spel du bjöd på. Det var en hög nivå på spelet och du höjde dig ytterligare efter andra set. Jag frågade dig efter matchen om du ens var trött, säger Medvedev till Nadal.