In recent years the development of eGovernment has increasingly gone from service provision to striving for an interoperable public sector, with Enterprise Architectures being an increasingly popular approach. However, a central issue is the coordination of work, due to differing perceptions among involved actors. This paper provides a deepened understanding of this by addressing the question of how differing interpretations of interoperability benefits affect the coordination in the early stages of implementing a public sector Enterprise Architecture. As a case-study, the interoperability efforts in Swedish eHealth are examined by interviews with key-actors. The theoretical framework is a maturity model with five levels of interoperability issues and benefits. The findings highlight the need to clarify decision-making roles, ambiguities concerning jurisdictions between authorities and that differing perceptions of IT-infrastructure is connected to overall goals. The paper also suggests a re-conceptualization of eGovernment maturity by moving away from sequential models.