Having missed a penalty against Burkina Faso at this year's African Nations Cup in Mali, Fortune bravely stepped up to take the vital spot kick against Paraguay.
"Sibusiso Zuma, who was brought down in the penalty area looked at me and said I should take it," Fortune said.
"Benni McCarthy would have taken it but he was substituted so I decided to do it myself."
The Paraguayans tried to unsettle Fortune by telling him he would shoot over the bar.
"I told them it's not a nice thing to do - I wouldn't do it to them. I just smiled and stepped up to take the penalty," the 25 year old midfielder said.
The joy of scoring his first goal was clearly evident in Fortune's jubilant celebrations.
"It's a great feeling to have finally socred for Bafana Bafana," he added.
"I was beginning to think the day would never come."