Under an age replacement policy, a stochastically failing unit is replaced at failure or after being in service for $t$ units of time, whichever comes first. An important problem is the estimation of $\phi^\ast,$ the optimal replacement time when the form of the failure distribution is unknown. Here, $\phi^\ast$ is optimal in the sense that it is the replacement time that achieves the smallest long-run expected cost. It is shown that substantial cost savings can be effected by estimating $\phi^\ast$ sequentially. The sequential methodology employed here is stochastic approximation (SA). When suitably standardized, convergence in distribution of the SA estimator to $\phi^\ast$ is established. This gives precise information about the rate of convergence. A sequential methodology introduced by Bather (1977) has roughly the same aims as ours, but it is not of the SA type. Rates of convergence apparently have not been established for Bather's procedure.