The objective of this study is to assess the capability and priority for Enterprise Architecture (EA) implementation in the context of Malaysian public sector agency. This study uses the Analytic Hierarchy Process (AHP) based on the judgments and opinions of EA team members from three different agencies at federal level. There are 27 assessment criteria which are grouped into six categories, Internal Process, Learning and Growth, Authority Support, Cost, Technology and Talent Management. The top capability of all cases is Internal Process and the top criteria for priority assessment is Authority Support. From the findings it can be concluded that AHP is a useful and cost effective method to assess, priorities and plan for EA implementation. Addressing the capability and priority criteria will ensure the optimum EA is implemented thus it shall reduce the risk of EA implementation failure.