A first Blues goal for Liverpool loanee Jordon Ibe as well as efforts from Andrew Shinnie and Nikola Zigic saw Birmingham clinch a first win in six.
Steve Morison equalised Ibe's opener in the first half while Simeon Jackson's 88th-minute penalty gave Millwall hope, but the Londoners are now winless in six at the Den and in deep trouble.
Millwall began the brighter of the two sides with frontman Morison, who was back in the team having been unavailable against parent side Leeds, leading the line.
First, he squeezed past Paul Caddis down Millwall's left but saw goalkeeper Darren Randolph save his initial shot and the follow-up from a tight angle.
Minutes later, he got on the end of Owen Garvan's miscued volley but, with Randolph just to beat, his curled effort from the left side of the area went over with the Blues defence demanding offside.
Despite being the better side for the opening 20 minutes, the hosts soon found themselves behind.
Following a defensive header, Chris Burke nipped in to win the ball and tee up Ibe, whose 20-yard shot beat David Forde diving to his left.
Millwall were level on half an hour however, as Scott McDonald's dinked pass found Morison in space down the left, and his well-struck shot - which appeared to be missing the target - hit defender Paul Robinson before going in.
However, the visitors regained the lead five minutes later as Tyler Blackett's left-wing cross was headed home by Shinnie from close range.
Ian Holloway threw on Jackson and Mark Beevers for the second half, replacing Alan Dunne and Shane Lowry, as Millwall chased only their second win in 12 games.
But they were denied what appeared a clear penalty soon into the half as Robinson blocked DJ Campbell's cross with an outstretched arm, much to the anger of the home players who demanded a spot-kick.
Their frustration was increased as Birmingham soon added to their lead. Burke sped past the outside of Martyn Woolford down the right and his chipped cross was met firmly by Zigic at the back post.
Garvan and Jimmy Abdou both miscued shots in reply as Millwall looked to score two goals in a game under Holloway for the first time.
Blues defender Aaron Martin then blocked a certain goal as Abdou looked like pulling a goal back from a shot inside the area.
Garvan planted a header wide in front of an open goal before Jackson reduced the deficit with two minutes to go with a cool penalty after he was fouled in the box by Martin, but there was no dramatic equaliser for the Lions.