The feature model is a reusable requirements model generated from the domain analysis. The reuse of feature models is usually achieved by a customizing-based approach. One important issue in feature models’ customization is the verification problem, caused by the fact that there are usually constraints among features, and that a valid customizing result must satisfy all these constraints. Because of the NP-hard nature of this problem, it is usually difficult to verify feature models in an efficient way. This paper presents a BDD (binary decision diagram)-based approach to verifying feature models by only traversing once to the nodes in BDDs, an approach that makes an efficient use of the BDD data structures based on the unique characteristics of feature models’ verification. It should be pointed out that this approach does not attempt to resolve the NP-hard difficulty of the verification problem in a general sense, but just tries to improve the scalability and efficiency of methods for feature models’ verification based on the utilization of this problem’s uniqueness. Experimental results show that this BDD-based approach is more efficient and can verify more complex feature models than the previous method.