Certificate verification and revocation are important aspects of public-key infrastructures (PKI). This paper presents the Tree-List Certificate Verification (TLCV) scheme, which uses a novel tree-list structure to provide efficient digital certificate verification. Under this scheme, users in a public-key infrastructure are partitioned into clusters and a separate blacklist of revoked certificates is maintained for each cluster. The verification proof for each cluster’s blacklist comes in the form of a hash path and a digital signature. An algorithm to derive an optimal number of clusters that minimizes the TLCV response size was described. The characteristics of TLCV were examined. Simulations were carried out to compare TLCV against a few other schemes and the performance metrics that were examined include computational overhead, network bandwidth, overall user delay and storage overhead. In general, we find that TLCV performs relatively well against the other schemes in most aspects.