It was the 46-year-old's 57th major title of her career and came 29 years after her first.
"
This goes beyond any wildest dream
"
Martina Navratilova
She and doubles expert Paes defeated Todd Woodbridge of Australia and Greek Eleni Daniilidou 6-4 7-5.
The Australian Open mixed doubles title was the only Grand Slam title which had previously eluded Navratilova in a career which began in 1973.
As Woodbridge hit the net on match point after 97 minutes, Navratilova screamed "yes", raised her eyes to the heavens and embraced her Indian partner.
The crowd gave her a standing ovation after she matched the feat of Australian Margaret Court who completed a sweep of titles at all the Slams in the 1960s before tennis turned professional.
"This goes beyond any wildest dream," said Navratilova, who was playing in her first Grand Slam final in almost eight years.
All-time Slam winners
"The support has been amazing. I'm sorry I haven't come back here for such a long time, but I guarantee it won't be another 13 years before I come back again."
Australia's Woodbridge, who has 18 Grand Slam titles including six in mixed, was in awe of his opponent.
"Martina is amazing - I had an opportunity to play with her at Wimbledon. I'm a little disappointed because she didn't play as well then," he said.
"She says she's still improving, so God help us all."
Navratilova's 57 Grand Slam titles place her second on the all-time list behind Court with 62.