Superfluidity is a manifestation of the operation of the laws of quantum mechanics on a macroscopic scale. The conditions under which superfluidity becomes manifest have been extensively explored experimentally in both quantum liquids (liquid 4He being the canonical example) and ultracold atomic gases, including as a function of dimensionality. Of particular interest is the hitherto unresolved question of whether a solid can be superfluid. Here we report the identification of a new state of quantum matter with intertwined superfluid and density wave order in a system of two-dimensional bosons subject to a triangular lattice potential. Using a torsional oscillator we have measured the superfluid response of the second atomic layer of 4He adsorbed on the surface of graphite, over a wide temperature range down to 2 mK. Superfluidity is observed over a narrow range of film densities, emerging suddenly and subsequently collapsing towards a quantum critical point. The unusual temperature dependence of the superfluid density in the limit of zero temperature and the absence of a clear superfluid onset temperature are explained, self-consistently, by an ansatz for the excitation spectrum, reflecting density wave order, and a quasi-condensate wavefunction breaking both gauge and translational symmetry.