For non-contiguous (NC) OFDM based cognitive radio (CR) systems, schemes have been developed in literature to acquire spectrum synchronization information (SSI) with perfect carrier frequency offset (CFO) synchronization. However, OFDM is extremely sensitive to the CFO in practice, which leads to inter-carrier interference (ICI), hence degrading the spectrum synchronization performance for existing schemes. An accurate CFO estimation is therefore required before setting up the SSI. In this paper, we present a novel scheme based on the maximum likelihood (ML) algorithm to estimate the CFO for the NC-OFDM receiver when the SSI is unknown. A corresponding Cramér-Rao lower bound (CRB) with the ideal SSI is derived to demonstrate the efficiency of the proposed scheme. Simulation results show that the proposed scheme is robust against interference and achieves a satisfactory accuracy of estimation, which is close to the relevant CRB.