Municipalities are key actors in planning and enabling the transition in the built environment to sustainable heat systems. Literature on the municipal experiences in the early phases of the heat transition is scarce. This paper addresses this gap by depicting the approaches of twenty-eight municipalities in the Netherlands. It aims to assess the municipal approaches to data collection, technology choice, and area prioritisation during the planning and (early) implementation stages and the barriers municipalities face. Identifying and choosing the optimal solutions per area requires numerous data, in-house knowledge and societal support. The lack of municipal capacity and know-how has led to a strong dependency on external expertise. District heating networks and heat pumps are presently seen as the most promising alternative systems, while building improvements are planned in areas when the technological choice is uncertain. Two important lock-in effects have hampered the local efforts to execute projects: a lack of binding policies to terminate natural gas use and poor affordability of the alternative heating systems. An overarching lesson is that the timely establishment of these aspects is critical to support the starting phase of the transition and that effective local governance cannot be achieved without centrally-established supportive mechanisms.