To improve the spectral efficiency of a full spectrum modulated nonlinear frequency division multiplexing (FS-NFDM) system, a blind frequency offset estimation (FOE) method has been proposed. The approach based on the minimum phase correction error can achieve high estimation accuracy of sub-MHz without need of any training symbols. Furthermore, in order to reduce the computational complexity, an eigenvalue-shift method is used to get a coarse search interval of FO, and then the one-dimensional optimization algorithm based on golden section search and parabolic interpolation is used to get the optimal FOE for the coarse search interval. The feasibility and reliability of the proposed blind FOE approach have been demonstrated in both BTB and fiber transmission scenarios. Compared with the grid search method, the proposed solving scheme can save hundreds of times of the searches. The experimental results reveal that the proposed method is robust to the amplified spontaneous emission noise and phase noise and has the capabilities of a wide FOE range and a high FOE accuracy.