Bound states at interfaces between superconductors and other materials are a powerful tool to characterize the nature of the involved systems and to engineer elusive quantum excitations. In-gap excitations of conventional s-wave superconductors occur, for instance, at magnetic impurities with net magnetic moment breaking timereversal symmetry. Here we show that interfaces between a superconductor and a quantum antiferromagnet can host robust in-gap excitations, without breaking time-reversal symmetry. We illustrate this phenomenon in a one-dimensional model system with an interface between a conventional s-wave superconductor and a one-dimensional Mott insulator described by a standard Hubbard model. This genuine many-body problem is solved exactly by employing a combination of kernel polynomial and tensor network techniques. We unveil the nature of such zero modes by showing that they can be adiabatically connected to solitonic solutions between a superconductor and a mean-field antiferromagnet. Our results put forward a new class of in-gap excitations between superconductors and a disordered quantum spin phase, including quantum spin-liquids, that can be relevant for a wider range of heterostructures.