Overseeing a qualifying campaign that features a 3-0 defeat at the hands of Finland, and just a single point from two matches against Azerbaijan, is never going to keep you in a job for long.
They had been brought up, after all, following teams, under the collective banner of Yugoslavia before the Balkans shattered into the fractured political map that exists today, boasting the talents of Dragan Stojkovic, Sinisa Mihajlovic, Vladimir Jugovic, Predrag Mijatovic and Savicevic himself.
After competing gamely as FR Yugoslavia at the 98 World Cup, to reach such lows once true independence had been garnered meant something had to change.
And so it was that new coach Ilija Petkovic, appointed in June 2003, steered Serbia & Montenegro in a direction that its football team had never before taken.
Once a byword for explosive, cultured play with a an often hot-headed, fiery edge, the country was to embark on a period of pragmatism; percentage football based on hard work and a resilient defence.
A difficult sell to a demanding public, no doubt, and a risky one at that. If you are to pursue such a policy you had better make sure you back it up with results. Thankfully for Petkovic, vindicated by comfortable qualification for this summer's event, he did.
An undefeated qualifying programme - Petkovic has yet to lose a competitive game as coach of the national team - built on the meanest defence in Europe saw Serbia & Montenegro qualify as group winners ahead of seasoned campaigners Spain and Belgium.
A solitary goal conceded in 10 games tells you all you need to know about where the side's strength lies; even that goal came in a hard fought 1-1 draw with Spain that all but guaranteed qualification.
'You cannot live by beauty alone,' suggests Petkovic, unashamedly abandoning the aesthetic heritage built by teams some of which he himself had played in. And whilst such a statement may alarm the football purist, it's hard to be critical of someone making the best of limited resources.
A strong team spirit is something Serbia & Montenegro appear to have in spades. But that will be tested by an exacting group that sees them up against Holland, Argentina and Ivory Coast.
In a region where it doesn't take much to provoke paranoia and suspicion, that such an outcome arrived after FIFA's strange decision to place Serbia & Montenegro in a pot by themselves during the draw has keep the conspiracy theorists busy ever since.
That the other pots were split on geographical rather than ranking lines perhaps legitimises their feelings of injustice. Having topped a qualifying group containing seeded Spain, the hand they were subsequently dealt only served to exacerbate their vexation.
Petkovic, however, was visibly unmoved at the ceremony and, perhaps reflecting the team's born-again confidence, was sanguine about events.
'This is a group of four excellent teams and there should be some great matches,' he said at the time. 'Perhaps it should be called the group of joy not the group of death.'
And he is right not to throw in the towel just yet. With each team capable of taking points off the other it will undoubtedly go to the wire. And it is not inconceivable that a win and a draw could be enough to see any of the four through to the next round.
Any sort of result from either of their first two games against Holland and Argentina, if there is a positive result when the two group favourites meet in their final match, should still see the Serbian-Montenegrins with something to play for when they take on Ivory Coast at the same time.
In producing during qualification a whole far greater than the sum of its parts, they have already proved capable of springing a few surprises.
The focal point of the attack is unmistakeable. At 6ft 8in, Nikola Zigic is a man that even Peter Crouch is forced to look up to. His effectiveness as a target man is undeniable, with strike partner Mateja Kezman the usual beneficiary of his flicks and knock downs.
The Red Star Belgrade giant is also adept at bringing others in to play and his game is not restricted to towering headers and physical presence alone.
There is one man who bridges the gap between the old and the new in terms of style.
In a team short on individual stars, Dejan Stankovic, of Inter Milan, is perhaps the best known and most generously gifted player in the squad. Often accused of saving his best form for Serie A, his willingness to knuckle down to more prosaic tasks on international duty commends him while his inventiveness will be essential if Serbia & Montenegro are to progress.
But it is the solid foundation upon which the team is constructed that offers greatest hope. Dubbed the 'Fantastic Four' after their nine clean sheets in 10 qualifying matches, a defence marshalled expertly by Schalke 04 centre-back Mladen Krstajic is a wall that will not be easily breached.
Even if a way can be found past the back four, Drogoslav Jevric, who plays his club football in Turkey, has proved himself a more than capable last line of defence.
Abandoning the sweeper system that characterised teams from the region in years gone by, Petkovic favours a flat 4-4-2 system with each man fully aware of his responsibilities to the team. In fact, the only deviation from a resoundingly conservative approach is an enforced one.
With little in the way of back up, the coach has given youth a chance in the squad with Dusan Basta, the Red Star defender and striker Mirko Vucini, of Lecce, having a busy summer with a trip to the Under-21 European Championships before they join up with the full squad.
So a settled side goes to Germany with little expected of them but with a self-belief that could be a valuable weapon in the weeks ahead. Don't expect it to be pretty but, if Greece taught us anything two summers ago, it was that artistic merit is no prerequisite for success at major tournaments.