We present a combined experimental and theoretical study of the evolution of the Fermi surface of the anomalous superconductor Pb$_{1-x}$Tl$_x$Te as a function of thallium concentration, drawing on a combination of magnetotransport measurements (Shubnikov de Haas oscillations and Hall coefficient), Angle Resolved Photoemission Spectroscopy (ARPES), and density functional theory (DFT) calculations of the electronic structure. Our results indicate that for Tl concentrations beyond a critical value the Fermi energy coincides with resonant impurity states in Pb$_{1-x}$Tl$_x$Te, and we rule out the presence of an additional valence band maximum at the Fermi energy. Through comparison to non-superconducting Pb$_{1-x}$Na$_x$Te we argue that the presence of these states at the Fermi energy provides the pairing interaction and thus also the anomalously high temperature superconductivity in this material.