R Ashwin was dismissed off the final delivery, as the match ended in a tie after 20 overs. Chennai finished on 136 for seven, in reply to Punjab's 136 for eight, forcing the contest to be decided in the Super Over.
Chennai batted first in the Super Over and put up just nine while losing two wickets to South African pacer Theron.
Matthew Hayden was bowled for a duck and Suresh Raina hit a six before he was out off a top edge, as Chennai lost both their wickets, scoring just nine in the
Chasing 10 for victory in the Super Over, Yuvraj Singh reverse swept Muttiah Muralitharan for a boundary to win the match for his team, after Mahela Jayawardene had hit the first ball for a six.
This is Punjab's first victory in the tournament after three straight losses.
Earlier, Parthiv Patel played a splendid innings of 57 from 58 balls, hitting four boundaries and two sixes, before he was stumped off Piyush Chawla.
That wicket saw Chennai lose their way, as three wickets fell for 27 runs in the last five overs.
Veteran spinner Muttiah Muralitharan was at his vintage best with the ball as he took three for 12 in four overs to restrict Punjab to 136 for eight in their 20 overs.
Yuvraj was the only batsman to make a sizeable contribution, scoring a quick 43 from 28 balls, while Irfan Pathan made 39 from 32 balls as the rest of the batting failed yet again.
Kings XI Punjab:
In a surprise move, Punjab sent in Irfan to open the batting with Ravi Bopara, after Chennai captain Suresh Raina had put them into bat. Pathan smashed 60 from 29 balls in a losing cause for Punjab against Deccan Chargers, and he started off in the same fashion. The left-hander hit Manpreet Gony for back-to-back boundaries in the second over through the off-side and leg side respectively in the second over of the match.
Pathan pulled a short delivery from Albie Morkel through the leg side for his third boundary. But it was Morkel who struck the first blow for Chennai, when he got Bopara caught at the third man boundary for 1, in the third over.
Captain Suresh Raina wasted no time in introducing spin and R Ashwin came in to bowl the fourth over; he conceded just three.
Gony suffered again at the hands of Pathan, who hit him for another couple of boundaries in the fifth over.
Kumar Sangakkara, on 4, got a lifeline when Gony failed to judge and hold on to a difficult chance on the third man boundary off Lakshmipathy Balaji in the sixth over.
Punjab failed to get going in the first few overs, scoring 41 for one after seven.
Sangakkara broke the shackles when he hit Ashwin back over his head for a boundary and Pathan then launched one over midwicket for a six, in the eighth over.
It was Muralitharan who gave Chennai their second wicket when he claimed Punjab captain Sangakkara. The left-hander charged down the wicket to Muralitharan, but was beaten in the flight and stumped for 15, as Punjab were reduced to 55 for two after nine overs.
Pathan tried to accelerate the run rate and looked to heave Balaji through the leg side. However, he could only manage to drag it back on to his stumps and was dismissed for a brisk 39 from 32 balls, as Punjab were left reeling at 59 for three after ten overs.
Muralitharan then dismissed another countryman to put Punjab in further strife. Bowling from round the wicket, he trapped Mahela Jayawardene leg before wicket for 3 as the visitors were reduced to 64 for four after 11 overs.
Yuvraj looked to hit his team out of trouble and pulled Morkel for a boundary, and then followed it up with a huge straight six against Ashwin in the next over.
The three quick wickets saw Punjab lose the initiative as they reached 98 for five in 15 overs, needing the make the most of the last five overs to post a competitive total.
Yuvraj went after Suresh Raina and lifted one over the covers for a boundary to race to 35 from 21 balls, in the 16th over.
Manvinder Bisla, playing at number seven, failed to get going before he was run out for 7.
With runs not flowing in the final overs, Yuvraj tried a huge shot down the ground against Morkel but holed out to the long-on fielder after a quickfire 43 from 28 as Punjab were reduced to 143 for seven in 19 overs.
The wickets continued to tumble as Suresh Raina scored a direct hit from covers to run-out debutant Juan Theron for a duck.
Piyush Chawla somehow managed to get a boundary in the final over as Punjab finished on a modest 136 for eight in 20 overs.
Except for Yuvraj's brisk 43 and Pathan's 39 no other batsmen made a decent contribution and struggled against Chennai's disciplined bowling attack.
Chennai Super Kings:
Matthew Hayden, playing with the conventional bat, hit a full delivery from Irfan Pathan over mid-on for a boundary in the first over of the innings.
Just like Chennai, Punjab brought in spin early, introducing off-spinner Ramesh Powar in the fourth over of the innings. Hayden wasted no time in going after the spinner and lofted him straight down the ground for a six; the next ball he was gifted a boundary when Yuvraj at mid-off failed to spot the ball.
Parthiv Patel welcomed Theron to the bowling crease with a cracking pull shot that crashed into the midwicket fence for a boundary. He repeated the dose on Irfan Pathan in the next over but this time got enough carry as the ball sailed over the fence for a six to take Chennai past the 50-run mark in the seventh over.
Piyush Chawla also got a taste of Hayden's power in his first over when the left-hander despatched him over long-off for his second six as Chennai reached 60 after eight overs.
Ramesh Powar gave Punjab the much needed breakthrough when he beat Hayden in the flight as he charged down and bowled him for 33 from 24 balls, including four boundaries and two sixes.
Patel played the hook shot to a short delivery from Shalabh Srivastava over the fine leg fence but shockingly the umpire called it a boundary; later it was rectified to a six. Captain Suresh Raina then slammed a full toss from Yuvraj over midwicket for his first six, as Chennai reached 91 for one after 12 overs, needing another 46 from the last eight overs.
But then things took a dramatic turn as Chennai lost three wickets in the space of three overs.
Raina was run out for 15 by a sharp piece of fielding from the bowler, Theron, who sprinted down the pitch on his follow through and kicked the ball on to the stumps.
In that same over, Murali Vijay was unlucky to be adjudged out leg before wicket for a duck as the ball was clearly heading down the leg side.
Chennai then lost another wicket when S Badrinath was caught behind off Yuvraj for 2 as the hosts slipped to 104 for four after 14 overs.
At the other end, Patel was having it easy as he completed his half-century, from 53 deliveries, with a single on the off-side against Powar in the 16th over.
But those three quick wickets saw Punjab's bowlers squeeze the flow of runs with a few tight overs in succession.
Just 13 runs came in three overs as Chennai reached 117 for four after 17 overs, but the hosts still had the game within their grasp as they need 20 from the last three overs.
Parthiv hit the first delivery off Chawla's next over for a boundary but then threw his wicket attempting a reckless shot.
Parthiv, who made 57 from 58 balls, charged down the wicket to Chawla but missed and was stumped by wicketkeeper Kumar Sangakkara.
With 16 needed from as many deliveries, Chennai surprisingly promoted Manpreet Gony up the order to take on the bowlers. Gony scored two from six deliveries as he looked to hit every ball out of the park before he was bowled by Theron as Chennai self-destructed.
With 10 needed from the last over, Morkel made the task easier when he edged a wide delivery from Pathan for a boundary through thirdman.
With three needed from the last three deliveries, Ashwin scampered for two runs on the off-side but he fumbled off the next delivery.
And with just one needed for a win off the final delivery, Ashwin showed no common sense at all as he chipped a full delivery straight to Kaif at mid-off instead of dropping it down and stealing a quick single.
The hosts finished on 136 for seven in 20 overs and the match ended in a tie. The Super Over was brought into play to decide the winner.
It was a pathetic batting display from Chennai's lower order as they choked towards the end and lost three wickets for 27 runs in the last five overs.
Theron displayed superb showing, claiming two for 17 in four overs, while Chawla also bowled intelligently in the final overs, claiming one for 27 in four overs.
(Super Over)
Chennai came out to bat in the Super Over with Hayden and Morkel taking strike, while debutant Theron was handed the ball after a superb performance earier.
Hayden fell for a first-ball duck but captain Raina lofted Theron into the stands for a six. He was dismissed off the next delivery, caught by Jayawardene on the off-side, as Chennai finished on nine for two in their Super Over.
Punjab started off well in their Super Over, Jayawardene hitting Muralitharan for a straight six. But off the very next delivery he tried to repeat the dose and was caught by Murali Vijay on the long-fence.
With four needed from four deliveries, the match was still up for grabs. Yuvraj was beaten off the third delivery as he tried the sweep, but the next delivery he took a risk and played the reverse sweep that went for a boundary through point. It clinched the match for Punjab.
Punjab finally ended their losing streak in the tournament and also registered their first win over Chennai in five matches.
Debutant Theron played a major role in Punjab's victory as he took two for 17 in his four overs and then kept his nerve to bowl a tight Super Over.
Chennai have themselves to blame after messing up in the closing stages; the math otherwise was looking like an easy run chase.
Punjab will be hoping this comeback victory can spur them to register more victories in the coming matches.