Neutron stars contain some of the densest matter in the known universe, with the maximal density in their cores greatly exceeding nuclear matter saturation density. Despite the fact that the theory governing the properties of neutron star matter - Quantum Chromodynamics - is well understood, obtaining accurate first principles predictions for the observable characteristics of neutron stars is surprisingly hard. In my talk, I will describe recent advances in this direction and in particular explain, how information about the equation of state of high-density deconfined quark matter, obtained using resummed perturbative QCD, can significantly aid solving the neutron star mystery.