The Next-to-Minimal Supersymmetric extension of the Standard Model (NMSSM) features extra new sources for CP violation. In contrast to the MSSM CP violation can already occur at tree level in the Higgs sector. We investigate the range of possible allowed CP-violating phases by taking into account the constraints arising from the measurements of the Electric Dipole Moments (EDMs) and the latest LHC Higgs data. Our analysis shows that large CP-violating phases, that are NMSSM-specific, are not in conflict with the EDMs. They are dominantly constrained by the Higgs data in this case. We use our results to investigate the prospects of measuring CP violation through the combined measurement of Higgs rates, on the one hand, and in observables based on CP-violating Higgs couplings to tau leptons on the other hand.