Validated policies can be utilized where information regarding the validation travels with the policies. A policy validator can validate information about a policy, such as may relate to compliance with policy requirements and accuracy of the policy output. Information about the validation, such as one or more claims of validity and information about the validator, can be provided with the policy as metadata, such as in a signature block. The signatures, or other verification mechanisms, can be used to ensure that the policy is not modified after the validation. When attempting to utilize the policy, the signature block can be evaluated along with the policy to determine whether to grant the access. In some embodiments the signature block may not be evaluated with the policy, but may be used subsequently for auditing or compliance determinations.