The objective of this paper is to analyze trade potential versus actual realized trade among North African trading partners. Following the literature on production economics, we built a stochastic frontier gravity model. The underlying assumption is that all deviation from trade potential is not due to white noise but could also be due to inefficiencies. Time-variant country-specific trade efficiency estimates are obtained and analyzed. Our results indicate that Mauritania as a country of destination and of origin is where the trading relationship is the least efficient. Conversely, Tunisia, followed by Morocco, faces the fewest “behind” and “beyond” the border effects. Our analysis of market integration and trade efficiency at the disaggregated level indicates that trade efficiency scores exhibit high variability between the categories of products. Moreover, North African market integration is worst when considering the goods from the category “Textiles; Footwear & Headgear”. Our estimates indicate that trade efficiency for agricultural products is relatively low indicating the existence of significant “behind” and “beyond” border inefficiencies. Our estimates also point at the presence of poor and counterproductive regulatory environment and underline the importance of improving domestic policies to encourage entrepreneurial development and business facilities. Our findings confirm the need for the North African countries to improve their trade logistics at the national level to enhance trade efficiency and to implement trade facilitation reform programs.