Han dömdes till döden den 5 november i år för att ha beordrat morden på 148 shiamuslimer i staden Dujail 1982.
Saddam Husseins advokater försökte in i det sista stoppa avrättningen. En amerikansk domare avslog begäran.
Avrättningen ägde rum i ett av Saddams egna gamla tortyrfängelser i Bagdad. Senare på lördagen flögs stoftet till hemstaden Tikrit och överlämnades till en klanledare, uppgav en advokat.
Själasörjare anlände
De sista förberedelserna för Saddam Husseins avrättning gjordes tidigt på morgonen i Bagdad.
En muslimsk själasörjare anlände för att vara med på avrättningsplatsen och höra fångens sista ord. Två vittnen fanns också på plats.
En av de personer som var officiella vittnen till avrättningen sade till Reuters:
-Det gick mycket fort. Han dog genast.
Han sade att expresidentens ansikte var obetäckt – det är annars vanligt att dödsdömda bär huvor när de hängs.
Verkade lugn
Saddam verkade lugn och läste en kort bön varefter de irakiska vakterna ledde honom till galgen och lade snaran om hans hals.
Premiärminister al-Maliki uppmanade dem som är engagerade i Saddams sunnitiska Baathparti att ompröva sin inställning och engagera sig i den politiska processen, rapporterar Reuters.
-Dörren är fortfarande öppen för var och en som inte har något oskyldigt blod på sina händer. De kan hjälpa till att bygga ett Irak för alla irakier, sade al-Maliki strax efter Saddams avrättning.
Enligt uppgifter i al-Arabiyya ska Saddams halvbror Barzan al-Tikriti och den före detta domaren Awad al-Bander, som dömdes i samma rättegång som Saddam, avrättas efter den kommande helgen Id al-Adha, som avslutas på torsdag.
Sen begäran om uppskov avslogs
Under natten avslog en amerikansk domare en sen begäran från Saddam Husseins försvarsadvokater om att avrättningen skulle skjutas upp. Advokaterna ville försöka hindra att amerikanska styrkor lämnade över fången till det irakiska rättssystemet mot bakgrunden av att Saddam Hussein står åtalad i ett civilmål i den amerikanska rätten och inte har haft möjlighet att försvara sig i denna.