Digitalization nowadays is a frequently used buzzword in private industries as well as in the public sector. Digital services are not rocket science anymore. The technology is ready and concepts for using them in public administration exist. Recently, e-government laws were enacted all over Germany to foster and structure the digitalization of administration. Basically every authority is affected by the regulations. So are the small and medium-sized municipalities. Their structure is heterogeneous: Many of them have a small administrative organization and suffer e.g. from small budgets and a lack of experts. To develop an understanding of what the specific challenges regarding digitalization in small and medium-sized municipalities in a federal system are, we conducted a series of 12 expert interviews across municipalities of different sizes in one German territorial state. The analysis of the answers provides an idea of the municipalities’ strategical and technical possibilities and their opinions on what would be beneficial for their further development in general and specifically with regard to the implementation of e-government laws. The acquired findings enable future research regarding a need for action and beyond to identify recommendations for action as well as to support municipalities in handling future digital challenges.