Federer's 6-7(5), 7-6(5), 7-5, 7-6(5) loss in exactly three hours rocked Wimbledon to its core on a day that already seemed surreal after seven players withdrew or retired injured and third-seeded Russian Maria Sharapova also stumbled to defeat.
The last time Federer, who has won a record 17 Grand Slam titles, including seven gilded Challenge Cups, failed to reach at least the last eight was in the 2004 French Open.
But on day three of the championships an opponent ranked a lowly 116th in the world launched outrageous winners to bring Federer to his knees and condemn the Swiss to his earliest Wimbledon exit since a first-round loss in 2002.
"I'm still in disbelief," said a sweat-drenched Stakhovsky. "When you play Roger Federer at Wimbledon, it's like you're playing two players. First you play Roger Federer and then you play his ego."
Federer's ego certainly took a battering on a day that started off routinely for the Swiss great as he nonchalantly ambled into the All England Club holding the hands of his twin daughters Myla Rose & Charlene Riva.
Facing an opponent who had never beaten a top 15 player would have rung few alarm bells but at 8.15 pm local time shock waves reverberated around the grounds when he slapped a backhand wide to leave Stakhovsky rolling in the grass in triumph..
Photograph: Mike Hewitt/Getty Images
Wimbledon PHOTOS: Federer cruises, fifth seed Errani bows out
Wimbledon: After the shockwaves, Serena restores order
PHOTOS: Sharapova, Wozniacki tumble out of Wimbledon
Forbes' MOST POWERFUL Celebs of 2013
Photos: Celebrities spotted at Wimbledon