Podenzana's compatriot Giuseppe Guerini was second, 37 seconds behind, and Peter van Petegem of Belgium was third, 50 seconds in arrears.
Bjarne Riis of Denmark retained the overall leader's yellow jersey -- coming in over five and a half minutes after Podenzana in the peloton.
Podenzana, on his first Tour despite being 34-years-old, had been part of a 28-man group that had escaped after only 10km.
Crossing the line, Podenzana raised his arms and then gave the sign of the cross in delight at winning the stage.
"It's wonderful. I took my chance because with all Van Petegem's fooling around at the back, I realised I would not win in a sprint finish with him," Podenzana said.
The original group of 28 had been reduced to just six after 38km. Podenzana was joined by Australian Neil Stephens, Guerini, Van Petegem, another Italian Michele Bartoli and Frenchman Francois Lemarchand -- who were left to fight the stage win out between themselves.
Podenzana, twice an Italian national champion, made his escape from the leading group with just over seven kilometres to the finish, realising he lacked the pace to win a sprint.
Though Stephens, winner of 33 races in his distinguished career, and Bartoli, winner of this season's Tour of Flanders, tried to get back on terms they were hindered by van Petegem who, while doing some of the late pacemaking, had earlier in the stage not helped out.
Van Petegem's TVM team wanted their team leader Jeroen Blijlevens to win the stage and hoped the peloton could catch the leaders. They gave instructions for Van Petegem to hinder the breakaway if he could.
Stephens then fell at a corner five kilometres from home, impeding Lemarchand and leaving the minor places to Bartoli, Guerini and van Petegem as Podenzana's bold move paid off.
Serge Beucherie, one of Lemarchand's management team from GAN, criticised TVM's tactics saying: "It is not in our style to not help the leading group -- unlike TVM.
"We have Frederic Moncassin challenging for the points winner's green jersey but we would still like to have won the stage and Lemarchand stood the better chance, so we helped."
Van Petegem defended his tactics.
"I wanted to help, but I wasn't allowed to by my boss. I would love to win a stage of the Tour de France, but if my team tells me not to help, what can I do?" he asked.
The peloton, led by Sunday's stage winner Djamolodine Abdujaparov's Refin team, never managed to reduce the gap to below five minutes.
Leader Riis was happy with the relatively easy day raced in intense heat of 32 degrees celsius.
"Tomorrow's stage on the Hautecam will be the moment of truth, and I feel very strong. I am in the form of my life," Riis warned.
The 199km stage from Agen to Lourdes-Hautecam contains a tough 1,500m climb at the end that could prove decisive with only five days racing remaining thereafter.
``I've had good moments in the Giro and the Italian championships but this is something else, this is the Tour,'' said the 34-year-old from La Spezia.
``This is the most important win of my career,'' added Podenzana, who escaped from a breakaway group 6.2 miles from the line at Villeneuve-sur-Lot in southwest France.
Twice an Italian champion, Podenzana enjoyed a time of glory by wearing the leader's pink jersey for nine days on the 1988 Giro.
He came close to winning a Tour stage last year when he finished second in Mende behind Frenchman Laurent Jalabert.
``There was no way I could win that day because Jalabert was too strong and also because he badly wanted the stage as it was Bastille Day in France,'' he said.
Podenzana, who has a reputation as a useful team mate, thought he might not take part in this year's Tour after his Italian team San Marco collapsed because of financial problems a few months before the race.
``I had very difficult start to my season and I never could imagine I would win a Tour stage,'' he said. ``In May I joined Carrera. They trusted me and allowed me to prepare well for this race.''
Knowing he had little to expect from three strenuous stages in the Pyrenees starting Tuesday, Podenzana timed his attack to perfection and none of the five other riders in his group could follow him.
His win comes as a welcome boost for Italian cycling, hit by the decline of former Tour front-runners Claudio Chiappucci and Gianni Bugno.
The best-placed Italian in the overall standings Monday was Leonardo Piepoli in a modest 16th place.
``I wouldn't call myself hopeful but I don't mind beating younger guys,'' Podenzana said with a smile. ``I was thinking about retirement but maybe I'll go on for one more year.''