International trade in services is hampered by non-tariff barriers that originate from national regulations. Not only the level of regulation in home or export country matters, but also the inter-country differences in regulation for service markets. Regulatory measures tend to affect fixed costs rather than variable costs. The fact that regulations often differ by market, means that the fixed costs of complying with regulations in an export market are in fact sunk marketentry costs. Our theoretical model demonstrates that policy heterogeneity between countries has a negative impact on bilateral service trade. We quantify bilateral policy variety through a new indicator that is applied in a gravity model for explaining service trade among EU countries. The empirical results support our theoretical prediction: the degree of regulatory heterogeneity is inversely related to the level of bilateral service trade. The results are applied to simulate the possible impacts of recent EU proposals for the services market. We find that making more use of mutual recognition could increase bilateral trade in commercial services among EU countries by 30% to 60%.