Troicki, the world number 30, eased past Michael Llodra 6-2, 6-2, 6-3, after Djokovic had crushed Gael Monfils 6-2, 6-2, 6-4 to pull his country level with his sixth win in six Davis Cup ties this season.
"It's the best moment of my life," said Troicki, who had lost Saturday's doubles alongside Nenad Zimonjic to Llodra and Arnaud Clement, forcing his team to face a nailbiting last day.
Djokovic marked the historic moment by having his head shaved courtside by his team-mates.
"It's history. It's our biggest success as individuals, as a team, as a country," said Djokovic, who had defeated Gilles Simon 6-3, 6-1, 7-5 on Friday after Monfils had given France the advantage with a 6-1, 7-6 (7/4), 6-0 win over Janko Tipsarevic.
On Sunday, Troicki had been called in to replace Tipsarevic in the crucial singles and the 24-year-old delivered in style, hitting 58 winners to Llodra's 32 in the 2hr 13min encounter.
Only briefly did he look like expectation might get the better of him when, at 4-1 ahead in the third set, he lost two quick games.
But he held his nerve to seal victory when his 30-year-old opponent was left flat-footed by a cross-court backhand winner.
Earlier, Djokovic comfortably sealed a sixth career win in six meetings with Monfils to set the stage for Troicki's fireworks inside a packed Belgrade Arena.
"It's one of the best matches of my career, in the circumstances," said Djokovic. "I have a lot of respect for the French team, especially Gael, who is a good friend."
In the first set, Djokovic broke Monfils twice as he surged to a quick 6-2 advantage.
The Serb broke Monfils again in the sixth game of the second set, and then in the final game, spreading his arms in mock triumph towards the increasingly vociferous partisan crowd as he surged to a 2-0 lead.
To his credit, Monfils upped his game in the third set, the world number 12 breaking Djokovic twice -- only to cancel that advantage by losing his own service game due to a series of unforced errors.
"I'm very disappointed, I expected to play a lot better," Monfils told France 3 television.
"I gave it everything I had. After talking to Guy (Forget, team captain) I tried to change tactics a few times because Novak was so strong.
"He was by far the better player today."