Polovojenské jednotky Fedayeenů byly založeny Saddámovým synem Udayem v roce 1995. V září roku 1996 byl Uday sesazen z velitelského postu, a to pravděpodobně kvůli konfliktu se svým otcem vyvolanému tím, že převedl v březnu téhož roku bez vědomí svého otce Fedayeenům část kvalitní výzbroje Republikánských gard. Velení převzal druhý syn Qusay, který tak posílil svoji moc nad bezpečnostním aparátem v Iráku. Velitelem jednotek se stal Mezahem Saab Al Hassan Al-Tikriti. Podle některých záznamů se velení později opět vrátilo Udayovi.

Jednotka Fedayeenů s celkovou silou mezi 18 a 40 tisíci vojáků je složena z mladých bojovníků z oblastí loajálních Saddámovi. Jednotka se zodpovídá přímo prezidentskému paláci a stojí mimo klasickou strukturu armádního velení. Je zodpovědná za hlídkování a protipašerácké kontroly. Ačkoliv je neprávem nazývána elitní jednotkou, Fedayeeni jsou politicky spolehlivou silou, se kterou je nutno počítat v boji proti domácím nepřátelům Saddáma Husajna. V počátcích to byla doslova banda venkovských balíků, kteří se postupně vypracovali na jednotku, jejíž cílem je ochrana prezidenta, Udaye a výkon špinavé práce za policii.

Součástí je i zvláštní "komando smrti", které má za úkol zabíjet nepohodlné osoby přímo v jejich domovech. Členové komanda operují mimo zákon a právní rámec země. Mezi jejich praktiky patří i veřejné popravy žen, kdy byly dotyčné přepadeny, vyvlečeny na ulici a před zraky svých dětí a ostatních členů rodiny i okolí veřejně popraveny setnutím hlavy.