They were plunged to defeat by goals from Emmanuel Adebayor and Thierry Henry, who once again confirmed his worth to the Arsenal side.
There was no Sol Campbell, who walked out on Arsenal in midweek, but manager Arsene Wenger confirmed that the big England defender will be back in training either Monday or Tuesday.
Even without Campbell it's obvious that the Gunners are going through a transitional period and the introduction of so many young players indicates the road down which Wenger is moving.
They have not really recovered from the departure of Patrick Vieira last year. His influence has been sadly missed as Arsenal have strived to find their winning style.
Wonder-boy Theo Walcott, who is still on trainee wages at Highbury, stepped up into the first-team squad following his arrival from Southampton a fortnight ago, but Wenger did not take the opportunity to give him a Premiership outing.
The new-look Arsenal were far from confident in the early stages when Birmingham were the more impressive as they made a determined to gain the upper hand.
Jiri Jarosik was a particular danger as he demonstrated with a powerful drive which Jens Lehmann pushed away for a corner.
The on-loan player from Chelsea had another reasonable chance of putting Birmingham ahead but he struggled to gain control and Arsenal survived a potentially dangerous situation.
Henry was far from happy with some of Birmingham's play and earned the first yellow card of the game for dissent. He continued to express his feelings and referee Mike Riley was lenient in as much he could have produced the red card.
Fortunately for Arsenal their skipper escaped the early walk back to the dressing room and made a major impact by creating the opening from which the Gunners went ahead in the 21st minute.
Henry mis-hit his cross shot which bounced off Birmingham's new central defender, Martin Latka, on to goalkeeper Maik Taylor and into Adebayor's path for him to score from close range.
The goal revived Arsenal and in particular Jose Antonio Reyes who emerged as the midfield general with some astute player that set up several promising attacks.
Birmingham, however, played a positive attacking game with Jermaine Pennant on form against his former club.
It was Pennant, who delighted the home fans with his brilliant skill, as he produced a fine cross to the far post where Heskey headed into the sidenetting.
As Birmingham went in search of the equaliser they were caught exposed by a vintage Henry goal in the 63rd minute.
Cesc Fabregas hit an accurate crossfield running pass into the path of Henry who moved effortlessly forward before stroking a low left-footed shot past Taylor.
Only the post prevented Matt Upson scoring from close range for Birmingham, which resulted in manager Steve Bruce sending on his latest signing DJ Campbell and Mikael Forssell.
The strikers replaced Muzzy Izzet and Jarosik, but even with four forwards the Blues could not breach Arsenal's defence as the Londoners held out for a solid win.