A novel two-stage n-PSK partitioning carrier phase recovery (CPR) scheme for circular multilevel quadrature amplitude modulation (C-mQAM) constellations is presented. The first stage of the algorithm provides an initial rough estimation of the received constellation, which is utilized in the second stage for CPR. The performance of the proposed algorithm is studied through extensive simulations at the forward error correction bit error rate targets of 3.8 × 10−3 and 1 × 10−2 and is compared with different CPR algorithms. A significant improvement in the combined linewidth symbol duration product (ΔνTs) tolerance is achieved compared to the single-stage n-PSK partitioning scheme. Superior performance in the ΔνTs tolerance compared to the blind phase search algorithm is also reported. The relative improvements with respect to other CPR schemes are also validated experimentally for a 28-Gbaud C-16QAM back-to-back transmission system. The computational complexity of the proposed CPR scheme is studied, and reduction factors of 24.5 | 30.1 and 59.1 | 63.3 are achieved for C-16QAM and C-64QAM, respectively, compared to single-stage BPS in the form of multipliers | adders.