Motivated by a simple theoretical model, this paper proposes a novel smooth-time-varying-parameter approach for estimating Okun's coefficients using U.S. quarterly data from 1948:Q1 to 2006:Q1. Despite Okun's coefficients depend on 'time' in an unknown (nonparametric) but smooth way, it can be estimated via the Bayesian approach, i.e., the Gibbs sampler, by treating the nonparametric line as additional unknown parameters to be estimated along with other model parameters. Empirical results show that there is overwhelming evidence in favor of smooth-time-varying Okun's law which is closely and positively (with lags) related to productivity trend. It also indicates that the commonly-used fixed-coefficient specification for characterizing Okun's law can lead to inappropriate, if not incorrect, results. (C) 2007 Elsevier B.V. All rights reserved.