International policy heterogeneity creates trade and investment costs for service firms doing business in other countries. Service providers have to comply with different rules in each foreign market where they operate. Complying with these regulations causes fixed market-entry costs, specific for each export market. We develop a new indicator for bilateral policy heterogeneity that is used as a proxy for the costs of policy heterogeneity. We explain bilateral services trade and services FDI in the European Union using a gravity model augmented with the heterogeneity indicator. We find a robust and strong negative impact of policy heterogeneity costs on services trade and FDI. The empirical results are used for assessing the potential impacts of the Services Directive proposed in 2004 by the European Commission. Several elements in the proposals would effectively reduce policy-related market entry costs for services providers. We project that the 2004 Services Directive could increase intra-EU services trade by 30% to 62% and direct investment in services by 18% to 36%.