This study investigates the systemic challenges facing enterprise architecture programs in government. Drawing upon the institutional theory lens from the political science field, a Danish case study is used to explore why public agencies implement enterprise architecture programs and the challenges they face when governing these programs at different levels (vertically) and different functions (horizontally) of government. The analysis shows that enterprise architecture is not just a technical issue, as economic and political facts are equally important when establishing interoperable e-government services. The findings suggest that implementing enterprise architectures in government challenges the way information systems are organized and governed in public agencies. Interoperability challenges in government arise because there is no overall coordination of different information systems initiatives in the public sector and because public organization have no economic and/or immediate political incentives to share data and business functionality with other organizations in their enterprise architecture programs.