AI-based and other complex technologies offer significant potential benefits for public administrations in turbulent environments—from reducing administrative burden through re-engineering existing processes to creating new value through new human-to-machine and machine-to-machine interactions. This potential has been recognized by public administrations around the world, with digitalisation and AI strategies highlighting the ambition of political and administrative levels to capitalize on the potential of technological initiatives. Estonia in its leading role with the provision of digital public services and a culture open towards innovation isn’t an exception. The latest digitalisation strategy “Estonia’s Digital Agenda 2030” has AI-based tools as the cornerstone for empowering the government. However, the transition from ideas on paper to solutions with widespread practical applications has been hampered by a variety of challenges. From legal challenges in ensuring privacy and accountability to organizational challenges in conflicts with values and ethics to technical aspects in availability and quality of data, the potential of novel technologies is shaped accordingly. This chapter focuses on three examples of designing and implementing AI-based tools in the Estonian public sector, a context supportive of technologically sophisticated initiatives. Through the analysis of challenges through change management and e-government perspectives, the chapter provides lessons and recommendations for the design and implementation of AI-based tools in the public sector.