Recognized as a critical factor for the whole-of-government capability, many governments have initiated Enterprise Architectures (EA) programs. However, while there is no shortage of EA frameworks, the understanding of what makes EA practice effective in a government enterprise is limited. This paper presents the results of empirical research aimed at determining the key factors for raising the maturity of the Government Enterprise Architecture (GEA) practice, part of an effort to guide policy-makers of a particular government on how to develop GEA capabilities in its agencies. By analyzing data from a survey involving 33 agencies, the relative importance of factors like top management commitment, participation of business units and effectiveness of project governance structures on the maturity of the GEA practice was determined. The results confirm that management commitment and participation of business units are critical factors, which in turn are influenced by the perceived usefulness of the GEA efforts.