Navratilova, in her last tournament, and fellow American Bryan beat Czechs Kveta Peschke and Martin Damm 6-2, 6-3.
It was a fitting way for Navratilova, who turns 50 next month, to hang up her racquet, her 59th grand slam title adding to a remarkable record that began when she turned professional in 1975.
She rose to the top of the women's game with serve-and-volley brilliance, accumulating 167 singles and 177 women's doubles titles. She was world number one for a total of 331 weeks.
Her grand slam haul includes 18 singles crowns, 31 women's doubles and 10 mixed doubles titles.
"It's entirely fitting, Martina that your last match would be winning another grand slam title," said US Tennis Association president Franklin Johnson in presenting Navratilova and Bryan with their trophy and a $150,000 cheque.
"I have so many memories," Navratilova, who won the first of her four US Open singles titles in 1983, said to a large Arthur Ashe Stadium crowd that stayed on after Maria Sharapova's singles triumph over Justine Henin-Hardenne.
"Thank you for a great ride," she said, echoing remarks made by Andre Agassi after his last career match earlier in the tournament.
"Like Andre said I'll take this memory with me for the rest of my life."
Bryan, who ended the match with an ace, said: "I congratulate you on the best tennis career of all time."
The Czech-born Navratilova, who became a US citizen in 1981, raised the level of the women's game after transforming herself from a podgy teen-ager to a supremely fit athlete who dominated the women's game.
Navratilova also had an impact off the court as WTA Tour players president for six years and as an openly gay athlete.
Navratilova has retired once before, in 1994, only to return in 2000.
This time, though, she says it is for real.
"This was the last match. No more. No more," she said.
Damm, who earlier on Saturday had teamed up with India's Leander Paes to win the men's doubles final, said he was thrilled to participate in the special occasion.
"I would like to congratulate Martina," Damm said. "It's been an unbelievable career.
"Obviously she has a lot of fans in the Czech Republic, where she was originally from, and I wish her the best in the after-life -- the tennis after-life."
More from rediff