In March 2009 and July 2010, the International Criminal Court (“ICC”) issued arrest warrants for the then Sudanese President Omar Al-Bashir on charges of war crimes, crimes against humanity and genocide. From 2003 to at least 2008, Al-Bashir’s government carried out a counter-insurgency campaign in Darfur using the country’s security apparatus. However, since his arrest depended on other state parties’ cooperation, Al-Bashir travelled freely for more than ten years. After years of stalemate, the possibility emerged that Al-Bashir would be tried in the Hague. However, the extent to which the Sovereign Council is committed to international accountability remains ambiguous. Even if Al-Bashir ends up at the ICC, his prosecution could prove considerably difficult. This article aims to shed light onto the greatest challenges the Office of the Prosecutor has already faced and will be facing if Al-Bashir is tried in Hague. It will explore the issue regarding Darfur’s referral to the ICC; Head of State immunity; non-cooperation by state parties to the ICC; Sudan’s commitment to complementarity; and the difficulty in linking the commission of genocide to Al-Bashir. Ultimately, it will explain how enforcing the rule of law in Sudan may be a long road ahead.