Results on the production of the double strange cascade hyperon Xi- are reported for collisions of p(3.5 GeV)+Nb, studied with the High Acceptance Di-Electron Spectrometer (HADES) at SIS18 at GSI Helmholtzzentrum for Heavy-Ion Research, Darmstadt. For the first time, subthreshold Xi- production is observed in proton-nucleus interactions. Assuming a Xi- phase-space distribution similar to that of A hyperons, the production probability amounts to PXi-=2.0+ or -0.4(stat)+ or -0.3(norm)+ or -0.6(syst)x10-4 resulting in a Xi-/(Lambda+ capital sigma 0) ratio of PXi-/PLambda+ capital sigma 0=1.2+ or -0.3(stat)+ or -0.4(syst)x10-2. Available model predictions are significantly lower than the measured Xi- yield.