Gareth Jenkins has been sacked as Wales head coach after his side crashed out of the World Cup.
Jenkins won just six of 20 games in charge of Wales
Jenkins was told of the Welsh Rugby Union's decision by chief executive Roger Lewis and chairman David Pickering at the team hotel on Sunday.
Lewis said: "No-one would deny the total commitment and passion that Gareth Jenkins has given to the cause.
"His desire for success has been tangible - you can taste it, you can smell it - but it was not to be."
Defeat by Fiji on Saturday ended Wales' World Cup campaign at the pool stage, but Jenkins had vowed not to resign.
He had a contract until the end of 2008 Six Nations, but the WRU has decided his position had become untenable.
Reaching the quarter-finals was the minimum requirement for Wales at the World Cup, but Saturday's 38-34 loss to Fiji in Nantes ended that goal.
The shock defeat was the 13th in 20 games for Jenkins, whose only wins of note in 16 months at the helm came against England and Argentina.
"The defining moment in this tenure was that we achieved a quarter-final place," said WRU chairman David Pickering.
"We give the coaching staff the opportunity to do it their way. Gareth said to us, 'I have had the opportunity to do it my way'.
"It is all about results and winning and we have fallen short. It is a huge disappointment for us all."
Pickering defended the swiftness of the decision to sack Jenkins, saying it was a necessity to avoid any "ambiguity" and "indecision".
This is not blaming one person, this is not about blaming Gareth Jenkins
WRU group chief executive Roger Lewis
A worldwide search has now been launched to find his successor, but Lewis said it was likely a caretaker coach would be in charge for Wales' next game against South Africa in Cardiff on 24 November.
Lewis also said the WRU will be undertaking a full review of elite rugby in Wales and inviting contributions from the players, coaches, regions and even from Jenkins himself.
The positions of assistant coaches Nigel Davies, Rowland Phillips, Neil Jenkins and Robin McBryde will be decided under that review.
"We have got to be totally focused that we don't find ourselves in this position again," said Lewis.
"We have got to be totally focused on ensuring we deliver what everyone wants in Wales and for Welsh rugby.
"Rugby defines us as a nation and unites us as a nation. It is important at this moment that rugby in Wales understands we have to focus together on making this work.
"This is not blaming one person, this is not about blaming Gareth Jenkins. All of Welsh rugby needs to look at itself and ask itself the tough questions.
"It needs to think, 'What are the right systems and structures that we need to have in place so we can compete at the highest level?'
"There is a collective responsibility for where we have arrived at today and there is a collective desire to ensure we don't arrive at this position in 2011."
Former Australia coach Eddie Jones and former South Africa coach Nick Mallett are early contenders to succeed Jenkins, while Wallabies attack coach Scott Johnson could also be tempted to return.
Johnson took over for three games as caretaker coach when Mike Ruddock resigned in February last year and recently expressed his desire to work again in Wales some day.