Successful e-government adoption in society depends mostly on trust among citizens who use it. It is vital to ensuring security of e-government applications and infrastructures as a guarantee of security and privacy of stakeholders in storing, processing and exchanging information over the online systems offered by the government. As threats on e-government information security are dynamic and continue to grow, policy makers need to perform evaluation on existing information security strategy to establish a trusted e-government service. This paper intends to propose a new method that can guide decision makers in evaluating strategic government information security. The evaluation framework is based on new Fuzzy Analytic Hierarchy Process that combines tangible and intangible factors as well as has specific capabilites to be used in vague and fuzzy decision environment which is common in information security related issues.