In Finnish, Swedish and Norwegian cities and urban regions, strategic approaches in urban planning have been developed by introducing different kinds of informal strategic plans. The means of improving the strategic quality of urban and regional planning have thus been searched from outside the statutory land use planning system, determined by the national planning laws. Similar development has also taken place elsewhere. When strategic plans are prepared outside the statutory planning system, these processes also lack the legal guarantee for openness, fairness and accountability. This is a serious legitimacy problem. In this article, the problem is examined theoretically and conceptually by combining democracy- and governance-theoretical perspectives. With this framework, four different approaches to legitimacy are derived: accountability, inclusiveness, liberty and fairness. The article concludes that strategic urban planning must find a balance between the four approaches to legitimacy. Concerning political processes, this requires agonistic acknowledgement of different democracy models, excluding neither deliberative nor liberalist arguments. Concerning administrative processes, it requires acknowledgement of the interdependence of statutory and informal planning instruments and the necessity of developing planning methods for their mutual complementarity—thus avoiding the detachment of informal strategic planning into a parallel planning “system”.