May-Treanor and Walsh took gold in Athens in 2004 and again in Beijing in 2008. No other beach volleyball team, men or women, have retained an Olympic title, let alone won a third.
At the end of the match, which finished 21-16 21-16, the two women fell to their knees face-to-face in the sand and hugged.
Then they got up, bathed in tears, and ran off in different directions to embrace family and friends, including Walsh's two young sons, and do high fives with Olympic volunteers.
Tokyo 2020
Top 5 beach volleyball moments at the Olympics
08/04/2021 AT 14:14
After a while, May-Treanor returned to the sand and performed a few solo dance moves, which she later described as "the shuffle".
"It's insane," said Walsh, her mascara smudged from tears.
"It doesn't feel like it's real. I told Misty when we were getting our medals, 'If I wake up tomorrow and we have to replay this match I'm going to be furious', because it feels like we're in a dream.
"It truly feels surreal. And it didn't feel like that the first two times, for whatever reason. But this is just, it's almost too good to be true."
Walsh was in tears throughout the medal ceremony, closing her eyes, throwing her head back and exhaling as she struggled to control her emotions. May-Treanor, who will now retire from competition, smiled and appeared relaxed on the podium.
Kessy and Ross, the 2009 world champions, were competing in their first Olympics. They have spent much of their careers in the shadow of Walsh and May-Treanor and the final was no exception. "They are the best team of all time," said Kessy.
The bronze medal went to Brazilian world champions Juliana Felisberta and Larissa Franca, who staged a dazzling comeback earlier to beat China's Xue Chen and Zhang Xi 11-21 21-19 15-12 after being within two points of losing.
Juliana and Larissa arrived in London as the favourites but their dreams of gold unravelled when they were upset in the semi-finals by Kessy and Ross on Tuesday.
The Brazilians were unable to play together at the Beijing Olympics in 2008 because Juliana was out with a knee injury.
Larissa teamed up with Ana Paula and they came fifth.
Despite the disappointment of missing out on the final, Juliana said a bronze was good enough to mark her outstanding partnership with Larissa. The duo have won the professional beach volleyball world tour six times.
"I cannot describe the sensation. I'm so happy," she said.
"Yesterday when I went to bed I said to Larissa, 'I'm really proud to play with you in the Olympic Games, it doesn't matter about the result but for the experience together it's wonderful'."
Xue and Zhang, bronze medallists in Beijing, had been expected to do better than in the last Games but they lost to May-Treanor and Walsh in their semi-final.
Like the Brazilians, the Americans said the unique bond between them was at the heart of their success.
"The bond we have, the understanding we have for each other is so special," said May-Treanor.
"The first two medals, the friendship we had was there, but it was more volleyall, volleyball. This was so much more about the friendship, the togetherness, the journey. Volleyball was just a small part of it."
It was a remarkable outcome for May-Treanor and Walsh, who spent more than two years away from the sport after their gold medal in Beijing.
Walsh had two baby boys less than a year apart, while May-Treanor was out with an Achilles injury picked up rehearsing for the TV programme "Dancing with the Stars" in 2008.
After lengthy soul-searching, the pair got back together in 2011 to try for a third gold.
The Olympic venue in London was a fitting setting for the pair to achieve their goal.
The 15,000-seat stadium, the biggest in beach volleyball history, is in the heart of London against the backdrop of the city skyline with the London Eye lighting up the night sky.
After rain-drenched semi-finals on Tuesday, the clouds cleared for Wednesday's matches and it was a perfect, starry night by the time May-Treanor and Walsh won the final.
Watching from the stands was Britain's Prince Harry, whose grandmother Queen Elizabeth resides a stone's throw away, at Buckingham Palace.
A delighted Juliana said the prince's presence had brought her luck, and her only regret was that he did not come along on Tuesday to help her win in the semis.
Ross and Kessy were equally excited by the royal visit.
"We actually watched him walk by today. We were coming through security," said Kessy.
Ross added: "We thought the cameras were for us because they were filming us walking. And then someone was like, 'Oh, Prince Harry's right behind you'."
A laughing Kessy added, "We were like, 'Oh, we're not that famous, are we?"
Rio 2016
Where has the crowd gone?
11/08/2016 AT 18:39
Rio 2016
Beach volleyball icon Randy Stoklos joined by other legends on Copacabana
10/08/2016 AT 16:38