The Premier League side were trailing 2-1 in the 83rd minute but their key midfielders stepped up to rescue a narrow victory for Roy Hodgson's men.
Paul Dickov looked to have been the star for the Foxes. The 35-year-old netted just 56 seconds into the second half and then set up Andy King two minutes later to put the League One side on course for what would have been a deserved win.
Hodgson made only one change to his Fulham side that beat Arsene Wenger's Arsenal on Saturday but they were completely outplayed by opponents two divisions below them.
And Dickov, in his second spell at Leicester, was key, firing home after Fredrik Stoor, making his debut, had made a hash of clearing a cross as the visitors attempted to recover from the injustice of being a goal down at half-time.
His persistence then robbed Brede Hangeland - who scored the only goal against Arsenal - to set up King, who curled in a beauty to send the away fans wild.
It was the least Nigel Pearson's side deserved after taking the game to their Premier League hosts, who needed two massive slices of luck to take a first-half lead.
Firstly Bobby Zamora failed to control a bouncing ball but it then rebounded back to him, allowing him to lay it back to Zoltan Gera.
The former West Brom man looked to be attempting a cross but it squirmed off the unlucky Michael Morrison and inside David Martin's near post as the Hungarian midfielder grabbed his first goal for the club.
And the Cottagers looked to be crashing out before Bullard, in one of Fulham's few moments of quality, played a one-two with Simon Davies before belting home from fully 25 yards.
It was then the turn of captain Murphy who, aided by a slight deflection, broke Leicester hearts in the third minute of stoppage time to complete the second incredible comeback of the second half.
Hodgson will breathe a major sigh of relief and will know that his side could easily have exited the competition at the first hurdle.