Mutola, the three-time world outdoor and seven-time world indoor champion, stormed to Olympic gold in the women's 800m at the 2000 Sydney Games.
And Semenya, likely to be South Africa's best prospect for gold at this summer's London Olympics, said her goal was to replicate Mutola's podium-topping performance in the British capital.
"With Maria a lot of things have changed," said Semenya, who won world gold in Berlin in 2009, and silver at the 2011 edition in Daegu, South Korea.
"In life you need to explore. I met with Maria before the last world championships and said I wanted something new.
"I started training with her after the worlds after splitting, with no hard feelings, with my former coach (Michael Seme).
"My goal is to win the Olympics. Maria's my role model, I'm looking to follow in her footsteps."
After her win in Berlin in 2009 Semenya found herself the target of seedy allegations that saw her cast into limbo because of doubts over her gender.
But she was cleared by the sport's world governing body, the IAAF, and largely accepted by her peers.
Semenya, who clocked a jaw-dropping personal best of 1:55.45 in storming to victory in Berlin, was stood down soon afterwards and remained on the sidelines until July 2010.
The Pretoria University student was revealed to be a hermaphrodite after the leaking of test results following her 800m win in Berlin.
The incident generated anger from the South African public and government, who rallied behind the athlete, and sparked a major gender review by the IAAF, which in April introduced new eligibility rules for women athletes with excessive male hormones, a medical condition known as hyperandrogenism.
Semenya was cleared to compete as a woman in July 2010, nearly a year after she shot to prominence, but she insisted on Thursday that the episode of her life was well behind her, adding she was happy as a role model in her country.
"Life wasn't easy, but I kept dealing with the situation with help from my family, friends and management. That made it easier for me," the 21-year-old said.
"Competition-wise, I'm competing, training is going well and the Olympics are coming. Life is good.
"It (the gender question) is not in my mind anymore. For me it's in the past. I have to focus on the future and that's what I'm doing right now."
And she said the gap in competition she endured after Berlin could have been crucial in her not getting closer to the world record of 1:53.28, the longest standing track and field mark set by Czech Jarmila Kratochvilova back in 1983.
"You just need hard work. Sooner or later it will be smashed, so I can't wait for that," Semenya said.
"I had a bit of a long break after the 2009 worlds and maybe if I had not had that long rest, I could have done that (broken the world record). My shape was okay, I just needed more races."
Semenya, who last month clinched her berth at the London Games, will be up against Kenya's defending Olympic champion and recently-crowned world indoor champion Pamela Jelimo.
"It's a good opportunity to run against the best. You always want to do our best," she said.
"Sometimes you need fast races, sometimes slow races. I can't wait for Friday's race to run against Pamela, she's the best in the world."
(For more sports news and updates, follow Ahram Online Sports on Twitter: @AO Sports)