The polynomial fitting method is used widely to detect cycle slips of carrier phases of GNSS for its easily computer programming and simple algorithm. But, this method is influenced by the observation errors and sampling rates. In this contribution, the polynomial fitting method and the Newton interpolation method are combined to solve those influences. In this paper, we introduce the new method theory and its mathematical model. Finally a test is taken to prove the reliable of the new method. The result shows that the new method does well in cycle-slips detection, and it reduces the calculation amount.