We show that the Schr{o}dinger-Newton equation, which describes the nonlinear time evolution of self-gravitating quantum matter, can be made compatible with the no-signaling requirement by elevating it to a stochastic differential equation. In the deterministic form of the equation, as studied so far, the nonlinearity would lead to diverging energy corrections for localized wave packets and would create observable correlations admitting faster-than-light communication. By regularizing the divergencies and adding specific random jumps or a specific Brownian noise process, the effect of the nonlinearity vanishes in the stochastic average and gives rise to a linear and Galilean invariant evolution of the density operator.