We study the concept of self-similarity with respect to stochastic time change. The negative binomial process (NBP) is an example of a family of random time transformations with respect to which stochastic self-similarity holds for certain stochastic processes. These processes include gamma process, geometric stable processes, Laplace motion, and fractional Laplace motion. We derive invariance properties of the NBP with respect to random time deformations in connection with stochastic self-similarity. In particular, we obtain more general classes of processes that exhibit stochastic self-similarity properties. As an application, our results lead to approximations of the gamma process via the NBP and simulation algorithms for both processes. (Less)