The Middle East North Africa (MENA) banking system has experienced significant developments in recent years. This is related mainly to deregulation of financial services, which lead to a debate on whether competition can improve the performance and efficiency of the banks. This paper tests four hypotheses that have been proposed in the literature on the relationship between market structure, profitability, and efficiency using stochastic frontier analysis with a panel data of the 201 banks in MENA countries during the period of 2005–2012. The empirical results show clearly that neither the structure conduct performance nor the efficient structure hypotheses hold in MENA countries. Our evidence goes with the relative market power hypothesis that suggests that banks higher market share are able to exercise their market power to obtain higher profits by setting higher prices. Furthermore, Cost efficiency has a significant effect upon bank profitability and the policy makers should adopt policies that promote further competition in the MENA banking sector.