It was 35-year-old Dion Dublin who was their late hero. Dublin, who these days plays in central defence after plying his trade as a striker for many years, popped up with the winning goal in the 90th minute to place more cup woe on the Addicks.
The former Cambridge United, Manchester United, Coventry City and Aston Villa striker scored with a glancing header from a Gareth Williams corner in front of 4,000 ecstatic Leicester supporters to deservedly give his team victory.
Charlton have a dismal recent cup record having been beaten on a number of occasions by teams from lower divisions. This was another repeat performance from a team who really fancied their chances of progressing having being drawn at home in all the rounds of the competition so far.
But Leicester dominated the first half and went in front when Nikos Dabizas headed home Joey Gudjonsson's free-kick.
Charlton, who had only Bryan Hughes' shot which was saved by Ian Walker to show for their first-half effort, were fortunate to equalise right on half-time when Shaun Bartlett flicked home Paul Konchesky's cross.
After their dismal first-half performance Charlton replaced Dennis Rommedahl at the start of the second half with Jerome Thomas, but still persisted with playing one striker. Alan Curbishley's side were overall out-fought by a Leicester side that has not been getting the rewards in the league that their performances have merited.
Keith Gillespie should have regained the lead for the Foxes three minutes after half-time when he had a header on the Charlton goal but he sent it straight into the arms of Dean Kiely in the home goal.
Then Charlton in a rare foray up front also missed a good chance when Hughes got on the end of a low left-wing cross only to send his shot spinning wide from just three yards out.
Leicester continued to control the game with their high tempo play and Charlton twice had to make last-ditch tackles to keep themselves in the match.
Dabizas, the Leicester goalscorer was unlucky not to get a second when Charlton keeper Kiely saved the former Newcastle United defender's close-range shot with his legs and Talal El Karkouri then scrambled Mark De Vries' shot off the line with his goalkeeper beaten.
It was justice when Leicester City scored the winner thanks to the oldest male on the field, Dublin, who headed home having come up from his central defensive position to find the net.
Charlton were marginally better in the second half than the first period but created few chances overall and didn't deserve to progress to the quarter-finals.
The deserved victory gives the Foxes, who were relegated from the Premiership last season, their moment of glory and a place in the last eight.
MAN OF THE MATCH: Dion Dublin (Leicester City) – Rolled back the years to produce a colossal display that he capped with a memorable late winner.