Two-dimensional (2D) crystals have emerged as a class of materials with tunable carrier density(1). Carrier doping to 2D semiconductors can be used to modulate many-body interactions(2) 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 superconductivity(6) and carrier mobility in devices(7). Here we report the discovery of Holstein polarons in a surfacedoped layered semiconductor, MoS2, in which a puzzling 2D superconducting dome with the critical temperature of 12 K was found recently(8-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 polarons(12-18). The short-range nature of electronphonon(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.