We show that observations of the core temperature of transiently-accreting neutron stars combined with observations of an accretion outburst give a lower limit to the neutron star core heat capacity. For the neutron stars in the low mass X-ray binaries KS 1731-260, MXB 1659-29, and XTE J1701-462, we show that the lower limit is a factor of a few below the core heat capacity expected if neutrons and protons in the core are paired, so that electrons provide the dominant contribution to the heat capacity. This limit rules out a core dominated by a quark color-flavor-locked (CFL) phase, which would have a much lower heat capacity. Future observations of or limits on cooling during quiescence will further constrain the core heat capacity.