Charlton took the lead in the 12th minute when the lively Brad Pritchard played the ball through to Rob Hulse and he thumped past Jason Steele from the edge of the box.
Chris Powell's men pushed on in search of a second as a Bradley Wright-Phillips strike deflected wide and Michael Morrison's overhead-kick failed to trouble the keeper.
It was all square in the 27th minute, though, when Jonathan Woodgate was left unmarked in the box and headed home Grant Leadbitter's inviting free-kick.
Johnnie Jackson was gifted the ball by Andre Bikey but lashed wide, while Hulse should have done better with a near-post header which went harmlessly over. Morrison also headed wide under pressure from Steele as Charlton continued to dominate as half-time approached.
Lawrie Wilson, who was struggling with a thigh problem in the closing stages of the first half, failed to reappear after the break, with Dale Stephens coming on.
Faris Haroun was denied by Ben Hamer, before sloppy play from Morrison in midfield allowed Josh McEachran to set clear Scott McDonald, who made no mistake from 12 yards.
Middlesbrough made the game safe in the 63rd minute with a route one goal. A long punt upfield from Steele was helped on by McDonald into the path of Emmanuel Ledesma and he lobbed the ball over Hamer from 20 yards.
McDonald was denied a second by a superb save from Hamer, while Charlton substitute Danny Haynes, back after injury, sent over a superb cross which only just eluded Hulse.
There was still time for Boro striker Lukas Jutkiewicz to hit a post before Richard Smallwood slid in to score a fourth and seal a memorable victory.