This paper selects the panel data of China’s education service exports to 76 countries from 2006 to 2018, uses the stochastic frontier gravity model to study the export efficiency and potential of China’s education service, and uses one-step method to analyze its influencing factors. The results show that the economic scale of China and student source countries, the population of student source countries, China’s FDI to student source countries, the number of universities in China, the number of Confucius Institutes, and the agreement on mutual recognition of academic qualifications all have a significant boosting effect on China’s education service exports. Geographical distance, cultural distance, and other factors that reflect the cost of studying abroad have a restraining effect. From 2006 to 2018, China’s education service exports only realized 62% of the export potential. Among them, the export efficiency to 7 countries including Qatar, the United Arab Emirates, and Kuwait was relatively low, and only less than 40% of the export potential was realized. Although the overall efficiency of China’s education service export to non-Belt and Road countries is higher than that of the countries along the “Belt and Road”, after the “Belt and Road” initiative was put forward in 2013, the export efficiency of China’s education services to countries along the Belt and Road has risen rapidly.