At a ceremony in Kabul, Petraeus passed the baton to John Allen, a former subordinate who made his name in Iraq by striking tribal alliances considered integral in reversing al Qaeda's momentum after years of appalling violence.
Lieutenant General Allen now becomes the first Marine to serve as head of the US-led war effort in Afghanistan.
Petraeus oversaw a surge of tens of thousands of troops into Afghanistan in a last-ditch bid to reverse a nearly 10-year Taliban insurgency and although he has claimed some progress, violence remains at record highs.
He is leaving to head up the CIA, after a week in which Afghan President Hamid Karzai saw his younger brother and a key aide assassinated at their homes, and as NATO began transitioning areas of the country to Afghan control.
Washington has now started to draw down troop numbers under a controversial timetable, which Petraeus has admitted he did not recommend, that has attracted widespread criticism for being too fast to hold onto tentative gains.
Celebrated in Washington for turning around the war in Iraq, Petraeus' legacy in Afghanistan, however, has been less clear.
Despite the surge, UN statistics released last week show that 1,462 civilians died in the first six months of 2011, an increase of 15%, and putting this year on track to be the deadliest in a decade.
Last Tuesday's killing of Ahmed Wali Karzai, probably the most powerful man in southern Afghanistan and younger half-brother of the Afghan president, has also been considered a threat to US gains against the Taliban in Kandahar.
Last night's killing of his senior adviser Jan Mohammad Khan, a former governor of southern Uruzgan province, in a raid on his Kabul home, has also been seen as another loss for the president.
The Taliban claimed responsibility for both the killings.
Petraeus took charge in Afghanistan in extraordinary circumstances after US President Barack Obama sacked his predecessor, Stanley McChrystal, over scathing remarks to Rolling Stone magazine about the US administration.
He is leaving at a time of great change in US personnel on Afghanistan. US ambassador to Kabul, Karl Eikenberry, is being replaced by another former Iraq veteran, Ryan Crocker, and Petraeus' predecessor at the CIA, Leon Panetta, has recently replaced Robert Gates as US defence secretary.
On the job, Petraeus oversaw his trademark counter-insurgency teachings which were deemed to have been so successful in Iraq, backed by a buildup of more than 30,000 extra American troops, now due to go home by the end of 2012.
But although the military is seen to have inflicted heavy casualties among the Taliban, particularly in the south, it has struggled to harness a tribal "awakening" of the type so instrumental in Iraq.
One day before Petraeus stepped down, a ceremony was held in central Bamyan province marking the start of a security transition from NATO to Afghan forces, a process that will see the departure of all foreign troops by 2014.
Analysts have already warned that the killing of Wali Karzai may trigger a turf war for control of the critical southern heartland that could embolden the Taliban and reverse NATO gains.
The killings, and a Taliban attack on the Intercontinental hotel in the heart of Kabul last month that left 21 dead, have fuelled doubts about the readiness of Afghans to manage national security.
After nearly 10 years of war, there are still around 150,000 foreign troops in Afghanistan, including nearly 100,000 from the United States.
Allen is a three-star general, described as cerebral and reserved. He was deployed in western Iraq from 2006 to 2008, where he played a key role in the pivotal "Anbar Awakening".
In Afghanistan, similar efforts to broker peace talks with insurgent leaders or woo Taliban fighters have yet to produce a major breakthrough.
COMMENTS
Comments are moderated and generally will be posted if they are on-topic and not abusive.
For more information, please see our Comments FAQ