This paper is the first to present a detailed modeling framework for measuring and comparing the relative efficiencies of mobile operators in the Middle East. Partial Factor Productivity together with three different DEA models, the CCR, the BCC and the A&P, using multiple inputs and outputs, are implemented to measure the efficiency of 16 mobile operators in nine different countries in the Middle East. The paper offers quantifiable suggestions on the improvements which the relatively inefficient mobile operators have to abide with to be able to compete with their regional counterparts. Seven mobile operators were found to have been functioning at full efficiency while 9 were operating inefficiently. The most efficient mobile operator among the 16 was Avea Turkey, followed by Etsialat UAE, Wataniya Kuwait, Turkcell Turkey, Mobily Saudi Arabia, Orange Israel and finally du UAE.