Heidfeld, who started third on the grid, had replaced India's Karun Chandhok in the team for the second season.
The other driver Brazilian Bruno Senna, who started seventh, finished 13th.
Both drivers gained a position before the first corner with Heidfeld challenging for the lead on many occasions. Due to complications during their car swaps, both drivers lost places in the pit stops.
Heidfeld rejoined the track in P4. Suffering from a broken rear wing, Nico Prost was forced to retire, promoting Heidfeld to P3 and the team's best result to date.
Also Read
"I want to thank the team for providing me a car that can achieve a result like this. I can be a demanding driver and as a team we pushed hard to get this result. We will build on this achievement, refine the car and I believe the M2Electro can continue to race at the front of the grid," Heidfeld said.
Team boss Dilbagh Gill said,"I don't quite have the words to describe what the first podium means to the team and to Mahindra. The performance of both cars in qualifying and Nick's final result shows that the approach we took to developing the M2Electro powertrain was the right one."