The objective of this study was to determine the optimum replacement policy for Holstein dairy herds in Iran using a dynamic programming model. Cows were described in terms of state variables that included milk production class, parity, pregnancy status, and month in milk with a 1-mo stage length. The objective function maximized the net present value of cows over a 15-yr planning horizon. Markov simulation was used to estimate expected herd dynamics under the optimal decision plan determined by dynamic programming. Stochastic elements included probabilities of pregnancy and abortion, production level, and involuntary culling. The optimum annual culling rate was estimated to be 31.4%, and cows had an expected herd life (time from first calving until culling) of 3.18 yr. High replacement cost and low carcass value resulted in only 2.87% voluntary culling (i.e., optimal model-based replacement). Assuming a heat detection rate of 0.4, cows averaged 2.8 services per lactation under the optimal policy. Sensitivity analyses were carried out to evaluate the effect of milk price, herd-average production, feed cost, heifer price, and carcass value on optimum replacement decisions. Herd-average production, replacement cost, and risk of involuntary culling were important factors affecting the optimal culling policy. Changes in the price of feed, calves, and milk and the probability of pregnancy had no considerable effect on the optimal policy considering the market situation in Iran during 2008.