Two-dimensional (2D) crystals have emerged as a class of materials with tunable carrier density1. Carrier doping to 2D semiconductors can be used to modulate many-body interactions2 and to explore novel composite particles. The Holstein polaron is a small composite particle of an electron that carries a cloud of self-induced lattice deformation (or phonons)3-5, which has been proposed to play a key role in high-temperature superconductivity6 and carrier mobility in devices7. Here we report the discovery of Holstein polarons in a surface-doped layered semiconductor, MoS2, in which a puzzling 2D superconducting dome with the critical temperature of 12 K was found recently8-11. Using a high-resolution band mapping of charge carriers, we found strong band renormalizations collectively identified as a hitherto unobserved spectral function of Holstein polarons12-18. The short-range nature of electron-phonon (e-ph) coupling in MoS2 can be explained by its valley degeneracy, which enables strong intervalley coupling mediated by acoustic phonons. The coupling strength is found to increase gradually along the superconducting dome up to the intermediate regime, which suggests a bipolaronic pairing in the 2D superconductivity.