This Letter presents the first experimental evidence of the attractive strong interaction between a proton and a φ meson. The result is obtained from two-particle correlations of combined p-φ p¯-φ pairs measured in high-multiplicity pp collisions at s=13 TeV by the ALICE Collaboration. The spin-averaged scattering length and effective range of the p-φ interaction are extracted from the fully corrected correlation function employing the Lednický-Lyuboshits approach. In particular, the imaginary part of the scattering length vanishes within uncertainties, indicating that inelastic processes do not play a prominent role for the p-φ interaction. These data demonstrate that the interaction is dominated by elastic p-φ scattering. Furthermore, an analysis employing phenomenological Gaussian- and Yukawa-type potentials is conducted. Under the assumption of the latter, the N-φ coupling constant is found to be gN-φ=0.14±0.03(stat)±0.02(syst). This work provides valuable experimental input to accomplish a self-consistent description of the N-φ interaction, which is particularly relevant for the more fundamental studies on partial restoration of chiral symmetry in nuclear medium.