The world number seven recovered from an error-strewn first set to win 3-6 7-5 6-3 making up for her disappointment in losing the 2000 final to Venus Williams.
Dementieva clenched her fists in celebration and then wiped away tears of joy after stopping the in-form Safina for the first time in four attempts this year.
"It's very difficult to explain the way I feel right now. It will take a few days before I realize I'm Olympic champion," Dementieva said.
Beijing 2008
Serena and Venus finish the job
17/08/2008 AT 12:13
"But this is for sure the biggest moment in my career, in my life. I will never forget this moment."
Russia had already been guaranteed the first tennis podium sweep in 100 years when Vera Zvonareva, a late call-up for the injured Maria Sharapova, clinched the bronze medal play-off against China's Li Na 6-0 7-5.
"Having three Russian girls left standing in the Olympics is a huge moment for Russia," Dementieva said.
"I know we were expecting and planning for some medals but I don't think anyone could expect three medals from the girls. So this is really big moment for Russia."
Meanwhile, 2000 doubles champions Serena and Venus Williams won their second title with a one-sided 6-2 6-0 win against Anabel Medina Garrigues and Virginia Ruano Pascual of Spain.
The sisters become only the second pair to win the women's doubles twice after fellow Americans Gigi Fernandez and Mary Jo Fernandez.
"The Olympics is truly about participation but it's also your moment in time," Venus Williams said.
"Today my moment in time was with my sister who I love almost more than anyone in the world. It's just amazing to think that we could participate and bring home a gold medal.
"I'm so excited I can't even speak."
Yan Zi and Zheng Jie bagged the bronze against Ukrainian sisters Alona and Kateryna Bondarenko, handing China their second successive women's doubles medal after Li Ting and Sun Tiantian's victory in 2004.
The singles final got off to a low-quality and bad-tempered start with neither player able to hold serve and frustrations growing on both sides of the net.
Safina screamed at herself before finally holding at 2-2 and then breaking at 3-2, prompting shrieks and angry racquet swipes from Dementieva as she went a set down.
Dementieva recovered her composure to take the advantage in the second set before Safina broke back at 2-4. Dementieva crucially held off a break point at 5-5 before levelling at one set each when Safina's backhand slice drifted wide.
Safina was furious when she was broken early in the tense decider, swiping the ball into the crowd. She broke back only to be broken again at 2-1 and this time took out her anger on her racquet.
Despite being broken again, Dementieva regained her two-game advantage when Safina hit a backhand into the net and the statuesque blonde closed it out on her first match point with a forehand winner.
Russia currently dominates women's tennis with five of the top 10 players and three of the last four Fed Cup titles.
French Open runner-up Safina, ranked just ahead of Dementieva at sixth in the world, had won all three meetings this year and came into the final on a 15-match winning streak.
The women's singles was hit by the withdrawal of Sharapova, then-number one Ana Ivanovic and 1996 champion Lindsay Davenport. Athens 2004 winner Justine Henin announced her shock retirement in May.
Factbox - Elena Dementieva
Age: 26 (date of birth: Oct 15, 1981)
Place of birth: Moscow, Russia
Career achievements:
Runner-up, 2004 U.S. Open, women's singles
Runner-up, 2004 French Open, women's singles
Semi-finalist, 2008 Wimbledon, women's singles
Semi-finalist, 2005, 2000 U.S. Open, women's singles
Previous Olympic results:
Silver medal, 2000 Olympics, women's singles
First round, 2004 Olympics, women's singles
Dementieva was formerly coached by Rausa Islanova – mother of fellow Russian Dinara Safina - whom she beat in Sunday's final. She enjoys playing chess, skiing and also used to have a cactus collection.
Beijing 2008
Stunning Nadal wins Olympic gold
17/08/2008 AT 09:41
Beijing 2008
Federer strikes gold in Beijing
16/08/2008 AT 15:23