Governments around the world are implementing artificial intelligence (AI) systems with varying success. The autonomous, learning, and inscrutable nature of AI technology suggests that organisations need to develop novel capabilities to ensure successful implementation. However, the understanding of what such capabilities are and how they can be developed is still emerging. This paper reports on qualitative case study research conducted on AI projects in three Australian public service domains: taxation, law enforcement, and healthcare. The findings point towards five distinct areas of capability that should be invested in: model development, domain understanding, model explanation, model integration, and model assurance. Each one has multiple dimensions which are discussed in detail, along with empirical insights on how the capability can be developed.