USA besprutade 12 miljoner liter av avlövningsmedlet över djungler mellan 1961 och 1971 under Vietnamkriget.
Vietnamesiska experter säger att mer än tre miljoner människor har drabbats av effekterna av herbiciden, av vilken omkring 400.000 dog.
Utvecklingen hyllas som en av de viktigaste i förbindelserna mellan Washington och Hanoi.
En ceremoni för att starta programmet hölls på Danang flygplats där avlövningsmedlet förvarades innan de besprutades över skogar gömmer kämpar från Viet Cong, gerilla backas upp av den kommunistiska regeringen i Nordvietnam.
Förbindelserna mellan USA och Vietnam har blomstrat sedan diplomatiska förbindelser upprättades för 16 år sedan och åtgärder för att lösa de problem som återstår från kriget har varit en hörnsten för framsteg, säger korrespondenter.
"Jag tycker det är rättvist att säga att dioxin kontaminering och Agent Orange var en av de enskilt mest neuralgiska frågorna i USA-Vietnam relation," sade USA laddning d'affaires Virginia Palmer.
I flera år diskuterade Hanoi och Washington frågan om ersättning till offren för avlövningsmedlet.
Men nu erkänner USA att dioxin, som finns i agent Orange, är ett mycket giftigt ämne.
– Studier tyder på att denna kemikalie kan vara relaterad till ett antal cancerformer och andra hälsoeffekter hos människor, säger det amerikanska ministeriet för Veterans Affairs.
För fem år sedan började ambassaden förskjuta fokus på att rensa upp dioxinhot spots, bana väg för snabba framsteg i vad som hade blivit den största kvarvarande krig-era frågan.
Den amerikanska kongressen tillgodosåg en initial $3m (Â £1.8m) under 2007 för ansträngningen och siffran har sedan stigit till $32m.
Vietnam och USA har tagit det första steget mot att rensa upp agent Orange smitta.