In this paper, we use a three flavor non-local Nambu--Jona-Lasinio (NJL) model, an~improved effective model of Quantum Chromodynamics (QCD) at low energies, to investigate the existence of deconfined quarks in the cores of neutron stars. Particular emphasis is put on the possible existence of quark matter in the cores of rotating neutron stars (pulsars). In contrast to non-rotating neutron stars, whose particle compositions do not change with time (are frozen in), the type and structure of the matter in the cores of rotating neutron stars depends on the spin frequencies of these stars, which opens up a possible new window on the nature of matter deep in the cores of neutron stars. Our study shows that, depending on mass and rotational frequency, up to around 8% of the mass of a massive neutron star may be in the mixed quark-hadron phase, if the phase transition is treated as a Gibbs transition. We also find that the gravitational mass at which quark deconfinement occurs in rotating neutron stars varies quadratically with spin frequency, which can be fitted by a simple formula.