Conventional approach for frequency estimation usually assume a single tone without data modulation. In many applications such an assumption, realized by using either a separate pilot beacon or synchronization preamble is not feasible. This paper deals with frequency estimation of phase-modulated carriers in the absence of timing information and known data pattern. We introduce new frequency estimators that are based on the generalized maximum likelihood principle. The communication channels under consideration include both additive white Gaussian noise (AWGN) channels and correlated Rician fading channels. For the latter class, we distinguish between the case when the fading (amplitude) process is tracked and that when it is not tracked.