Superconductivity usually emerges from a metallic normal state which follows the Fermi-liquid paradigm. If, in contrast, the normal state is a fractionalized non-Fermi liquid, then pairing may either eliminate fractionalization via a Higgs-type mechanism leading to a conventional superconducting state, or pairing can occur in the presence of fractionalization. Here, we discuss a simple model for the latter case: using a combination of perturbation theory and functional renormalization group, we show that the Kitaev-Kondo lattice model displays a fractionalized superconducting phase at weak Kondo coupling. This phase is characterized by Cooper pairing of conventional electronic quasiparticles, coexisting with a spin-liquid background and topological order. Depending on the sign of the Kitaev coupling, we find the pairing to be either of chiral d-wave or p-wave type for extended doping regions around the van Hove filling. We discuss applications and extensions.