NbSe2 is a remarkable superconductor in which charge-density order coexists with pairing correlations at low temperatures. Here, we study the interplay of magnetic adatoms and their Yu–Shiba–Rusinov (YSR) bound states with the charge density order. Exploiting the incommensurate nature of the charge-density wave (CDW), our measurements provide a thorough picture of how the CDW affects both the energies and the wave functions of the YSR states. Key features of the dependence of the YSR states on adsorption site relative to the CDW are explained by model calculations. Several properties make NbSe2 a promising substrate for realizing topological nanostructures. Our results will be important in designing such systems.