Safina, urged on by her brother Australian Open champion Marat Safin, lost the opening set before staging a spirited comeback to beat the world number one.
"This is undoubtedly the biggest win of my career so far," said the 19-year-old. "Until now I've never beated the world's top player."
Safina now takes on France's third seed Mary Pierce, who survived six match points against another Russian, Elena Likhovtseva, to win 7-5, 4-6, 7-6 after nearly three-and-a-half hours.
Anastasia Myskina, who had been gunning for a Kremlin Cup hat-trick after winning back-to-back titles here, also tumbled out of the $2.3 million tournament, going down to her Russian Fed Cup team mate Elena Dementieva 6-2, 6-3 in a re-match of last year's final.
Fourth-seeded Dementieva, looking for her first title in Moscow, will face unseeded Italian Francesca Schiavone, who continued her giant-killing run by dispatching 2004 U.S. Open champion Svetlana Kuznetsova 6-3 6-1.
Schiavone knocked out second seed Amelie Mauresmo on Thursday.
A nervous-looking Sharapova escaped defeat against Anna-Lena Groenefeld in the second round on Wednesday when the unseeded German retired because of an ankle injury while leading 6-1, 4-2.
The Florida-based 18-year-old, playing the Moscow event for the first time, controlled her nerves much better on Friday.
Sharapova, wearing a white-and-green top with a black skirt, came out firing, breaking Safina three times to seal the first set in 31 minutes.
The second set was more evenly balanced until Safina earned a decisive break in the 10th
FIGHTING INSTINCTS
A 12,000-strong crowd at the Olympic sports complex began pulling for Safina midway through the second set.
Safina raced into a 5-1 lead in the decider before it was time for Sharapova to show her fighting instincts.
The world number one won the next four games but Safina eventually secured victory on her third match point.
"I think today I played much better, especially in the first set, than in my first match on Wednesday," said Sharapova.
"In the second set I broke her in the seventh game to lead 4-3 but she broke right back and she looked a lot more confident after that.
"In the end it was one or two points which decided the outcome but what can I say, life goes on," she added.
"I'm going home to Florida to have some rest and get ready for the WTA Championships (in Los Angeles)."
Safina said it was the support of the home crowd which had pulled her through.
"Anywhere I looked I saw a familiar face," she said. "On one side it was my brother, then I turn around and see my coach or (Mikhail) Youzhny's brother. Everyone was cheering me on and I felt I just can't lose in such circumstances."
Likhovtseva led 6-0 in the final-set tiebreak of her match but somehow allowed Pierce to win the next eight points for a sensational comeback.
"In tennis it's never over till it's over," said a relieved Pierce, the French and U.S. Open finalist this year.
"I think once before I was 6-2 down (in a tiebreak) and won but never from 6-0."