We advocate a Bayesian approach to optimal quantum frequency estimation - an important issue for future quantum enhanced atomic clock operation. The approach provides a clear insight into the interplay between decoherence and the extent of the prior knowledge in determining the optimal interrogation times and optimal estimation strategies. We propose a general framework capable of describing local oscillator noise as well as additional collective atomic dephasing effects. For a Gaussian noise the average Bayesian cost can be expressed using the quantum Fisher information and thus we establish a direct link between the two, often competing, approaches to quantum estimation theory