A Certificate Management System (CMS) is used to generate, distribute, store and verify certificates. It supports secure electronic communication through its functions. In a CMS, the integrity of every certificate that a security application relies upon must be verified. The certificate verification function performs the verification process and can store verified certificates in the local database for later use. Focusing on the certificate verification function, this paper presents a state-based model for CMSs and discusses certificate verification issues. A recursive approach to certificate verification is proposed, and several verification techniques, which may be employed to reduce the amount of work in the verification process, are also presented.