This Letter presents the first experimental observation of the attractive strong interaction between a proton and a multistrange baryon (hyperon) Ξ-. The result is extracted from two-particle correlations of combined p-Ξ-S.p-Ξ+ pairs measured in p-Pb collisions at sNN=5.02 TeV at the LHC with ALICE. The measured correlation function is compared with the prediction obtained assuming only an attractive Coulomb interaction and a standard deviation in the range [3.6, 5.3] is found. Since the measured p-Ξ-S.p-Ξ+ correlation is significantly enhanced with respect to the Coulomb prediction, the presence of an additional, strong, attractive interaction is evident. The data are compatible with recent lattice calculations by the HAL-QCD Collaboration, with a standard deviation in the range [1.8, 3.7]. The lattice potential predicts a shallow repulsive Ξ-interaction within pure neutron matter and this implies stiffer equations of state for neutron-rich matter including hyperons. Implications of the strong interaction for the modeling of neutron stars are discussed.