Enterprise Architecture is seen as instrumental to drive the digital transformation in enterprises. It is also important to achieve the benefits from innovative new business models and technologies. Many organisations have therefore undertaken extensive efforts to implement Enterprise Architecture (EA). It is, however, a challenging task to implement enterprise architecture in an organisation. There is also very limited research on this issue related to the public sector. This study explores the implementation of enterprise architecture (EA) in the Norwegian Labour and Welfare Administration – NAV. While the study revealed that NAV had not defined any clear benefits, we found 12 perceived potential benefits. We also uncovered 16 challenges that impeded the EA implementation.