It is well known that D-brane instantons can generate contributions to the effective superpotential of gauge theories living on D-branes which are perturbatively forbidden by global U(1) symmetries. We extend this idea to theories with supersymmetry breaking, studying the effect of D-brane instantons stretched between the SUSY-breaking and visible sectors. Analogously to what happens in the SUSY case, this mechanism can give rise to perturbatively forbidden soft terms (among other effects). We introduce and discuss general properties of instanton mediation. We illustrate our ideas in simple Type IIB toroidal orientifolds. As a bi-product, we present a string theory realization of a Polonyi hidden sector.