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 gases1, 2, including as a function of dimensionality3, 4. Of particular interest is the hitherto unresolved question of whether a solid can be superfluid5, 6. 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.