The focus of this paper is on trend estimation for a general state-space model Yt=μt+ɛt, where the dth difference of the trend {μt} is assumed to be i.i.d., and the error sequence {ɛt} is assumed to be a mean zero stationary process. A fairly precise asymptotic expression of the mean square error is derived for the estimator obtained by penalizing the dth order differences. Optimal rate of convergence is obtained, and it is shown to be “asymptotically equivalent” to a nonparametric estimator of a fixed trend model of smoothness of order d−0.5. The results of this paper show that the optimal rate of convergence for the stochastic and nonstochastic cases are different. A criterion for selecting the penalty parameter and degree of difference d is given, along with an application to the global temperature data, which shows that a longer term history has nonlinearities that are important to take into consideration.