The Kondo effect and superconductivity are both prime examples of many-body phenomena. Here we report transport measurements on a carbon nanotube quantum dot coupled to superconducting leads that show a delicate interplay between both effects. We demonstrate that the superconductivity of the leads does not destroy the Kondo correlations on the quantum dot when the Kondo temperature, which varies for different single-electron states, exceeds the superconducting gap energy.