When Barack Obama came to power, the Middle East took part in worldwide celebrations. His Cairo speech was regarded by many analysts as the starting point of a new American policy towards the « Muslim world ». However, American legitimacy in the Middle East is in a deep crisis since the end of the USSR. Unlike the Cold War era, the US is no longer in a position to gain legitimacy by fighting communism. Local public opinions could accept this necessity back then but nowadays the configuration is widely different. One of the consequences of the end of communism is that the US is not regarded as a « defensive » actor anymore, but as an « oppressive » one. The political confrontation is so fierce that it calls for a true political « new deal » and not a simple PR operation.