The Mojahedin-a Khalq is a radical opposition movement that calls for the destruction of the Islamic Republic of Iran. Between 1980 and 2001 they mustered violent attacks from their military bases in Iraq against the Iranian regime, and also against Iranian embassies in Europe. This placed them on the U.S. and EU’s list of terrorist organizations in 1997 and 2002. They were disarmed in 2003 after the U.S. led invasion of Iraq. MEK and their political wing, the National Council of Resistance of Iran, are led by husband and wife Maryam and Massoud Rajavi, who are accused of leading a personal cult. Their ideology is based on Massoud Rajavi’s secular interpretation of Islam. Due to their violent past and relationship with the late dictator Saddam Hussein, MEK have lost most of their support in Iran and in the international community. However, they are popular among many high-ranking officials in Europe and the U.S. because of their fight against an authoritarian regime. This study analysis what strategies MEK apply in their search for legitimacy, and how effective these strategies are for seeking recognition in and out of Iran. I discuss why MEK fail to rebuild legitimacy in spite of fighting an unpopular regime. I find that the primary reason for this is that they lack credibility due to inconsistencies in their strategies.