The Addicks went ahead through Bryan Hughes after 19 minutes, and defender Jonathan Fortune added a second two minutes before half-time.
But Hughes headed his second a minute later before Danny Murphy scored with an inswinging free-kick on 64 minutes.
Charlton have been embarrassed by the likes of Oxford, Luton, Walsall and Gillingham in recent seasons.
Rochdale boss Steve Parkin:
"In the first half I think we showed them a bit too much respect.
"We also conceded a couple of bad goals and we haven't been doing that in the league in recent weeks.
"It would have been nice once we got it back to 2-1 to last a little bit longer but they scored another goal so quickly and that killed it."
Charlton: Kiely, Young, Fortune (Fish 74), El Karkouri,Hreidarsson, Thomas, Euell (Murphy 45), Holland, Hughes,Johansson (Konchesky 79), Jeffers.Subs Not Used: Andersen, Rommedahl.
Goals: Hughes 19, Fortune 44, Hughes 56, Murphy 64.
Rochdale: Gilks, Evans, Burgess, Heald, Goodall,Clarke (Warner 76), Bertos, Jones, Cooksey (McGivern 86), Holt,Tait (Atieno 68). Subs Not Used: Edwards, Gallimore.
Goals: Holt 51.
Ref: R Beeby (Northamptonshire).