The paper empirically investigates whether a lack of competition determines the poor productivity performance of the European business services. It uses detailed panel data for 13 EU countries over the period 2000-2005. We apply parametric and nonparametric methods to estimate the productivity frontier and subsequently explain the distance to the productivity frontier by market characteristics, entry- and exit dynamics and national regulation. We find that the most efficient scale in business services is close to 20 employees. Scale inefficiencies show a hump-shape pattern with strong potential scale economies for the smallest firms. Nonetheless, some 95% of the firms operate at a scale below the minimal optimal scale. While they are competitive in the sense that their productivities are very similar, they have strong scale diseconomies compared to the larger firms. Their scale inefficiency is persistent over time, which points to growth obstacles that hamper the achievement of scale economies. Regulation characteristics explain this inefficiency, particularly regulation-caused exit and labour reallocation costs are found to have a large negative impact on productivity performance.