The holders rued a number of missed chances in the second half to be one of several Clydesdale Bank Premier League casualties in the second round of the competition.
Kilmarnock, who beat Celtic 1-0 in last season's final, threw everything at the Irn-Bru Scottish Second Division side in 90 minutes but Stenhousemuir held on at Rugby Park.
In a quiet opening quarter, the visitors looked dangerous in their 4-2-3-1 counter-attacking formation with the towering John Gemmell providing a huge target up front.
Stenhousemuir had the first effort in the fifth minute when Gemmell laid the ball sweetly off to Iain Thomson who had broken from midfield - but his long-range effort from 25 yards flew aimlessly over the crossbar.
On 19 minutes, Gemmell's presence inside the penalty box won Stenhousemuir a penalty kick, after Ryan O'Leary held the striker's shirt. The defender was booked and Brown Ferguson stepped up to calmly send goalkeeper Kyle Letheren the wrong way.
The Second Division side were brimming with confidence and Gemmell tried a speculative 30-yard half-volley which went sailing over the bar, before Bryan Hodge's left-foot shot minutes later was deflected by Michael Nelson to take the ball inches wide of the post.
But Kilmarnock created the best chance of the first half in the 38th minute when Danny Racchi created space on the right-hand side and drilled the ball across the face of goal, only for Jude Winchester to miss an open goal from six yards out.
The holders were made to rue that missed chance five minutes later, when Ferguson's deep corner-kick was misjudged by Letheren and the ball was headed into the empty net by Gemmell from a few yards out.
Kenny Shiels introduced tricky winger James Dayton at the interval and immediately the Englishman was involved in a quick, passing move that set up Rory McKenzie - who saw his low shot held by Callum Reidford.
However, Stenhousemuir's back-four was rigid and forced the home side into long-range efforts, with Nelson trying his luck just after the hour mark, only for his effort to be held by Reidford. Minutes later, midfielder Racchi then sliced a volley a few inches too high from the edge of the 18-yard-box.
The 2,000-strong home support grew frustrated as Kilmarnock struggled to create openings in the second half. Shiels opted for an expansive four-man attack that left a number of glaring gaps in their defence.
With a quarter of the game to play, the SPL side produced another long-range effort through McKenzie, but the lively forward saw his right-foot effort from 25 yards rattle Reidford's left-hand post.
And as Kilmarnock threw everything against the Corrigan's side, defender Mark O'Hara created space on the flanks with some quick feet but his low cross was diverted wide by O'Leary from inside the six-yard box.
The part-timers were camped inside their own half for long spells in the last 20 minutes, as Kilmarnock lifted the intensity of their passing moves.
Substitute William Gros showed a neat turn of pace inside the Stenny half and rifled another 30-yard effort into the palms of Reidford - but the visitors' fresh legs from the bench made them a potent threat on the counter-attack and second half sub Darren Smith held the ball well before curling a 25-yard shot past the far post.
Shiels' attacking reshuffle, including central defender Nelson, increased the pressure on Stenny and the Englishman headed home Dayton's free-kick with the game heading into injury-time.
And Kilmarnock came within inches of taking the game to extra-time when James Fowler played a neat one-two with O'Hara inside the box and amongst an almighty scramble just yards from goal, the injured Reidford clutched the ball in his gloves - before the referee blew the whistle to end a frantic affair.