Depending on the density reached in the cores of neutron stars, such objects may contain stable phases of novel matter found nowhere else in the Universe. This article gives a brief overview of these phases of matter and discusses astrophysical constraints on the high-density equation of state associated with ultra-dense nuclear matter.