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.