Osieck was informed of the decision to end his three-year tenure by Football Federation Australia (FFA) shortly after the heavy defeat.
FFA chairman Frank Lowy said: "The decision is based on the longer term issues of the rejuvenation of the Socceroos team and the preparations for the World Cup and the Asian Cup.
"FFA has set a strategic objective of having a highly competitive team in Brazil and then handing over a team capable of winning the Asian Cup on home soil in January 2015.
"We have come to the conclusion that change is necessary to meet those objectives.
"I thank Holger for his contribution to Australian football and wish him well in his future endeavours."
Australia have already booked their place at next year's World Cup finals, but Osieck come under increading pressure following a nervous qualification campaign.
Since then a second successive 6-0 reverse - Australia lost by the same scoreline against Brazil last month - proved the final straw for FFA to act.
Osieck and the players were informed of the decision two hours after the final whistle in Paris.
Socceroos midfielder Tim Cahill tweeted: "Want 2 say Thankyou to Holger for getting us to our 3rd WORLD CUP. Is this a first get us to WC and get the sack. Sad day for Football in oz"
The decision comes less than nine months before next summer's World Cup finals, but was not unexpected after speculation in Australia that FFA had begun to sound out a new manager.
One of the names reportedly on FFA's wish-list is former boss Guus Hiddink, who came in at short notice to lead the Socceroos to the 2006 World Cup, where they reached the knockout stages.
Hiddink is a fan favourite in Australia and is out of work after he resigned as coach of Russian side Anzhi Makhachkala in July.
Assistant coach Aurelio Vidmar will be in charge for their next match in London on Tuesday night against Canada - coincidentally the only national team Osieck has previously managed.
The 65-year-old German was brought in shortly after the last World Cup in South Africa, when an ageing Socceroos squad was blamed for a group-stage exit.
Osieck, who was Franz Beckenbauer's assistant when Germany won the 1990 World Cup, initially had success leading Australia to a 2-1 win over his home nation in Monchengladbach while also steering the Socceroos to the final of the Asian Cup in 2011.
Qualification for the World Cup was not straightforward, however, and a shock loss to Jordan midway through the campaign left them on the brink of disaster as he kept faith in experienced players.
A late run of results eventually sealed Australia's place at a third successive World Cup finals, although it was only confirmed by an 83rd-minute Josh Kennedy header in the final game of their qualification campaign at home to Iraq.
Osieck's perceived over-reliance on the last remaining 'Golden Generation' of Australia's players was at the heart of the criticism he faced and following Friday night's defeat - when he handed a starting debut to Borussia Dortmund goalkeeper Mitch Langerak - he had said he would not walk away from his position.
"That's not my call," he told Fox Sport Australia.
"Two heavy losses of that extent gives some food for discussion (about my job).
"The merits of the past are forgotten when this happens."