Previous studies pointed out that the determination of the optimal exercise boundary is an important element in the valuation of American options. A correct understanding of the behavior of the optimal exercise boundary is crucial for the valuation of American options. In this paper, the properties associated with the optimal exercise boundary in a binomial option pricing model are examined and an efficient recursive valuation method which incorporates these properties is presented. This valuation method represents a substantial improvement over the conventional binomial model in terms of computational efficiency with exactly the same accuracy.