The Pat Lam-coached visitors had shot into an early 13-3 lead and produced a stirring backs-to-the-wall effort in trying to contain the reigning RaboDirect PRO12 champions.
But having lost Ronan Loughney (70 minutes) and Kieran Marmion (76) to the sin-bin, Connacht's wilting scrum was unable to keep Leinster at bay and the hosts snatched the win from the jaws of defeat.
The westerners - winless in Dublin since September 2002 - went 10 points up with scrum half Marmion poaching a 13th minute try and Dan Parks kicking the rest of the points.
Madigan's third successful penalty closed the gap to four points right on half-time, but Leinster had to bide their time against an aggressive Connacht defence.
The scoreline remained 13-9 until the dying minutes when Connacht leaked a succession of penalties - 18 in all - and Leinster's forward power, aided by replacement tighthead prop Martin Moore, edged it for them.
There were only two minutes on the clock when Parks drilled over a right-sided penalty from inside the 10-metre line. Leinster started without Sean O'Brien (ankle), with Shane Jennings taking his place at openside flanker.
Connacht's solid start continued as they tackled aggressively to chop down both Fergus McFadden and Dave Kearney, and Parks drove home a penalty from halfway for 6-0.
The returning Madigan punished a scrum infringement from Jake Heenan to get Leinster on the scoreboard, splitting the posts with a confident strike from the right.
Connacht failed to take advantage of a five-metre scrum after a Madigan kick was charged down by Craig Ronaldson, but Leinster then blundered on their own scrum ball to gift Marmion the opening try.
The alert Connacht scrum half reached out to score after the visitors got the push on in the set piece, with Jamie Heaslip and Eoin Reddan both unable to control the loose ball and Noel Reid beaten to it on the line by Marmion.
After Parks converted from close range, a promising Leinster attack was foiled by a Luke Fitzgerald knock-on and there was some concern for a prone Madigan, who was hit hard by Robbie Henshaw, before he got back on his feet.
Slashing runs from Mata Fifita and McFadden saw both sides attack with vigour in an open, exciting first half, the hosts picking up the pace noticeably as Madigan landed his second penalty following a Henshaw offside.
Leinster pressed for more approaching the interval and while Connacht defended heroically, they did leak a late penalty - Craig Clarke was pinged for not rolling away and Madigan mopped up with an important three points.
Clarke, Heenan and Brett Wilkinson were all having big shifts for Connacht, who signalled their intent on the restart when turning down a kickable penalty.
Lam's charges worked a lineout maul and Wilkinson went close before Kevin McLaughlin infringed near the whitewash, but Parks' poor penalty attempt came back off an upright and Leinster had a real let-off.
Madigan was just short with his own penalty attempt from halfway, and with man-of-the-match George Naoupu getting on the ball Connacht doggedly held onto their slim advantage.
Although handling errors from Gavin Duffy and Matt Healy invited Leinster forward, Connacht somehow survived a spell of scrum pressure near their line.
The proceedings were decidedly stop-start entering the final quarter as a succession of penalties broke up play. Leinster's hopes were boosted when replacement prop Loughney was sin-binned with 10 minutes left.
Leinster shunned a shot at the posts as they looked for their set piece to decide the game. Marmion duly saw yellow for interfering with Isaac Boss at the base of a scrum and a couple of collapses led to the vital penalty try.
LEINSTER SCORERS: Penalty try, I. Madigan (1 conversion and 3 penalties)
CONNACHT SCORERS: K. Marmion (1 try), D. Parks (1 conversion and 2 penalties)
15: Rob Kearney (Zane Kirchner, 71)
14: Fergus McFadden
13: Luke Fitzgerald
12: Noel Reid (Jimmy Gopperth, 71)
11: Dave Kearney
10: Ian Madigan
9: Eoin Reddan (Isaac Boss, 71)
1: Jack McGrath
2: Sean Cronin (Aaron Dundon, 77)
3: Michael Bent (Martin Moore, 55)
4: Devin Toner
5: Quinn Roux (Mike McCarthy, 46)
6: Kevin McLaughlin (Rhys Ruddock, 55)
7: Sean O'Brien
8: Jamie Heaslip CAPTAIN
REPLACEMENT NOT USED: Jack O'Connell.
CONNACHT: G Duffy; T O'Halloran, R Henshaw, C Ronaldson, M Healy; D Parks, K Marmion; B Wilkinson, S Henry, R Ah You, M Swift CAPTAIN, C Clarke, M Fifita, J Heenan, G Naoupu.
REPLACEMENTS: D Heffernan, JP Cooney, R Loughney, A Muldowney, A Browne, P O'Donohoe, D Leader, F Carr.
REFEREE: David Wilkinson (IRFU), ASSISTANT REFEREES: Mark Patton, Barrie O'Connell (both IRFU), 4th OFFICIAL: Gary Conway (Leinster Rugby Referees), 5th OFFICIAL: Gareth Crawford (Leinster Rugby Referees), TMO: Alan Rogan (IRFU).
|Leinster Rugby Score Card|
|Connacht Rugby Score Card|
Blues v Leinster
Cardiff Blues v Leinster Rugby
Cardiff Blues (A)
01/10/2016, KO 19:35
Sat 1st Oct 16
BT Sport Cardiff Arms Park
Blues 13-14 Leinster
L W L W W
W W W W W