We present the first stellar spectroscopy in the low-luminosity (M_V ~-9.3 mag), dwarf galaxy Leo P. Its significantly low oxygen abundance (3% solar) and relative proximity (~1.6 Mpc) make it a unique galaxy to investigate the properties of massive stars with near-primordial compositions akin to those in the early Universe. From our VLT-MUSE spectroscopy we find the first direct evidence for an O-type star in the prominent HII region. The spectroscopic confirmation of such a massive star supports arguments that the upper limit to the initial mass function, even if sparsely sampled, is not signficantly influenced by the low star-formation rate of Leo P. We classify 14 further sources as massive stars (and 17 more as candidate massive stars), most likely B-type objects. From comparisons with published evolutionary models we argue that the absolute visual magnitudes of massive stars in very metal-poor systems such as Leo P and I Zw 18 may be fainter by ~0.5 mag compared to Galactic stars. We also present spectroscopy of two carbon stars identified previously as candidate asymptotic-giant-branch stars. Two of three further candidate asymptotic-giant-branch stars display CaII absorption, confirming them as cool, evolved stars; we also recover CaII absorption in the stacked data of the next brightest 16 stars in the upper red giant branch. These discoveries will provide targets for future observations to investigate the physical properties of these objects and to calibrate evolutionary models of luminous stars at such low metallicity. The MUSE data also reveal two 100pc-scale ring structures in Halpha emission, with the HII region located on the northern edge of the southern ring. Lastly, we report serendipitous observations of 20 galaxies, with redshifts ranging from z=0.39, to a close pair of star-forming galaxies at z=2.5.