The implementation of the General Data Protection Regulation within the European Union intensifies regulatory requirements in terms of data protection for Smart City services. In particular, the mandatory Data Protection Impact Assessment (DPIA) process constitutes a complex managerial challenge. To reduce the complexity, this study develops a typology of Flemish Smart City services based on DPIA costs. Our explorative case study, based on face-to-face interviews and a workshop, shows that DPIA costs vary along the complexities of i) the urban environment in which a Smart City service is provided, and ii) the Smart City service itself. The research further demonstrates that these complexities represent multilayered concepts. The complexity of the urban environment consists of three layers: i) city size, ii) diversity of urban stakeholders, and iii) total of Smart City services in the urban region. Similarly, the complexity of the Smart City service is composed of five layers: i) number of different data streams, ii) clarity of data ownership, iii) amount of use-cases, iv) privacy invasiveness, and v) visibility of the Smart City service. While most layers of the respective complexities unequivocally matter in the eyes of the experts, others are more contested, such as the size of the city and the visibility of the Smart City service. This cost-based framework is of value to city administrations and Smart City service providers as it allows them to make the DPIA process more efficient by shortening the learning curve and improving decision making by clustering services based on data protection needs. In particular, stakeholders that have little expertise in-house, and that are looking for an easy-to-understand, rational framework can benefit from these results. Furthermore, based on both the literature review and the obtained results, our systematic data protection impact-cost-approach is generalizable beyond the EU-borders.