Khedira supplied Özil and then got on the end of a brilliant return pass from the little playmaker before finishing past Hugo Lloris in the 74th minute to hand Germany their first victory over their neighbours since reunification.
The last time France had lost to a German team was back in 1987, when Rudi Völler scored twice in a 2-1 West Germany victory.
It looked like Les Bleus' impressive run against their old foes would continue when Mathieu Valbuena headed the hosts in front at the Stade de France just before half time.
However, a cool finish from Thomas Müller brought the visitors level within six minutes of the restart, and Joachim Löw's side then soaked up second-half pressure before securing a confidence-boosting win.
"In the first-half we had a good system, but we conceded an unlucky goal. We've probably got our winners mentality back," said Müller.
Khedira said that they didn't deserve to trail but the right team had prevailed eventually.
"It was unnecessary to concede the goal, but you can't keep the French quiet for 90 minutes," he said. "We gave the right answer in the second half."
Defeated France coach Didier Deschamps said basic errors had cost them.
"We played some good stuff going forward, but were punished for our mistakes, especially at their equalizer. We kept pushing right to the end, but unfortunately it wasn't to be."
While the Germans were missing a whole host of regular starters, their's was still the more experienced of the two teams at international level.
Manuel Neuer, Bastian Schweinsteiger and Miroslav Klose were among the stars that German coach Joachim Löw was unable to call upon, but the likes of Müller and Özil can still be magnificent to watch when in full flow.
Those two combined to produce the first chance of the night in the sixth minute, as Müller sliced through the middle of the home defence before feeding Özil, who tried to go round Lloris, only for the alert France goalkeeper to get down well.
Giant Arsenal central defender Per Mertesacker then saw his header turned on to the bar and over by Lloris soon after.
However, the home side, which was close to full strength, eventually came back into things, led by the attacking flair of Franck Ribery and Karim Benzema.
A brilliant breakaway by Ribery -- who was in direct opposition to his Bayern Munich colleague Philipp Lahm on the left wing -- ended with Valbuena firing over, and moments later Benzema found himself through on goal with just goalkeeper Rene Adler to beat.
However, the Hamburg shot-stopper, making his international comeback after more than two years out of the fold, foiled his effort, with Benzema appearing unable to believe that he was onside.
The fact Germany had conceded a 4-4 draw with Sweden in their last competitive outing indicated that their defence is not as watertight as it has been in the past, and France went on to find a way through just before the half-time whistle.
The German backline was slow to react when Benzema rattled the woodwork with a free-kick from long range, and Moussa Sissoko teed up Marseille's Valbuena -- the smallest man on the pitch -- to head in.
However, the visitors did not need long to draw level after the restart, with the impressive Ilkay Guendogan playing in Mueller to score after French half-time substitute Etienne Capoue had ceded possession.
France then had chances to retake the lead, with Valbuena firing narrowly over from the edge of the box and Ribery turning a Benzema cross just past, but Khedira's strike made it 2-1 and sparked joyous celebrations from Löw on the German bench.