Kournikova, 20, who has been attempting another comeback after missing much of the year with a foot injury, was bundled out of the $2.185 million tournament by the 17-year-old wild card ranked only 251st in the world in 75 minutes.
It was Fokina's first ever win on the WTA Tour, while Kournikova has lost all her singles matches following her comeback.
The world No. 20 was beaten by fellow Russian Anastasia Myskina in the first round of the Leipzig Grand Prix last week and lost her opening match to Australia's Nicole Pratt in San Diego in July.
But Kournikova's latest defeat was the most lopsided.
The U.S.-based Kournikova, who lost to Martina Hingis in last year's final, was whistled off the court after a performance riddled with unforced errors and double faults.
"I think lately many Russians don't seem to like Anna that much, therefore I felt like I had more fan support than her and I didn't feel nervous playing on center court," Fokina said.
However, Kournikova was not too disappointed with the loss.
"I've lost three matches since I had my injury in February, and all of those came in three sets," she said.
"I'm still trying to regain my physical fitness and mental strength, so my game is bound to have its ups and downs," she added.
"People talk a lot about me dropping out of the top 10 or even the top 20, but I honestly don't really care what my ranking is.
"All I can do is continue playing tournaments, then start getting ready for next year."
Kournikova also did not think much of her opponent.
"She is a young player and has a lot to learn. Obviously from looking at the scoreline, her game lacks consistency," she said. "It wasn't the best match to watch by any means."
Fokina will now face fifth-seeded Jelena Dokic after the Yugoslav overcame Russia's Lina Krasnoroutskaya 6-3, 5-7, 7-5 in a seesaw battle between teenagers.
Third seed Roger Federer of Switzerland, who followed Kournikova on center court, became the latest high-profile casualty in the men's event as he bowed out to German Nicolas Kiefer 6-3, 1-6, 7-6.
Federer, who shocked Pete Sampras in the fourth round at this year's Wimbledon, saved one match point in the third-set tiebreaker but on the next point hit a forehand long to hand the match to his 40th-ranked opponent. It was Federer's 43rd unforced error.
Nicolas Escude was another seed to fall in the first round earlier in the day as the eighth-seeded Frenchman succumbed to 85th-ranked Swede Magnus Gustafsson 6-4, 5-7, 6-4.
Meanwhile, Russian top seed and defending champion Yevgeny Kafelnikov had little trouble dispatching teenage compatriot Mikhail Youzhny 6-3, 6-3 in the first meeting between the two players.
It was a good day for the Swedes in the Russian capital as fifth seed Thomas Johansson beat Italy's Davide Sanguinetti 6-2, 6-3 and compatriot Thomas Enqvist overcame another Italian, Andrea Gaudenzi, 6-7, 7-6, 6-1.
In other first-round women's matches, eighth-seeded Yelena Dementieva beat fellow Russian Yelena Bovina 6-3, 6-4 and now takes on another qualifier, American Alexandra Stevenson, who eliminated Anne Kremer of Luxembourg 6-2, 6-3.
A Message from The Moscow Times:
Dear readers,
We are facing unprecedented challenges. Russia's Prosecutor General's Office has designated The Moscow Times as an "undesirable" organization, criminalizing our work and putting our staff at risk of prosecution. This follows our earlier unjust labeling as a "foreign agent."
These actions are direct attempts to silence independent journalism in Russia. The authorities claim our work "discredits the decisions of the Russian leadership." We see things differently: we strive to provide accurate, unbiased reporting on Russia.
We, the journalists of The Moscow Times, refuse to be silenced. But to continue our work, we need your help.
Your support, no matter how small, makes a world of difference. If you can, please support us monthly starting from just $2. It's quick to set up, and every contribution makes a significant impact.
By supporting The Moscow Times, you're defending open, independent journalism in the face of repression. Thank you for standing with us.
Remind me later.