This paper tests four related theories on the relationships among market structure, profitability, and efficiency using a stochastic frontier analysis and dynamic panel data for 201 banks in Middle East and North Africa (MENA) countries during the 2005–2012 period. The results show that neither the structure–conduct–performance hypothesis nor the efficient structure hypothesis holds in MENA countries. This finding has important implications, meaning that the performance of the financial sector can be obtained under competitive and efficient conditions without high levels of concentration. The evidence also supports the relative market power hypothesis, suggesting that banks with higher market share obtain higher profits by setting higher prices. Furthermore, we find that cost efficiency has a significant effect on bank profitability, but also there are still highly concentrated markets in which banks are less profitable and more inefficient, adversely affecting the competitiveness of the banking system