A super-persistent chaotic transient is characterized by the following scaling law for its average lifetime: tau approximately exp[C(p- p(c))(-alpha)] , where C>0 and alpha>0 are constants, p > or = p(c) is a bifurcation parameter, and p(c) is its critical value. As p approaches p(c) from above, the exponent in the exponential dependence diverges, leading to an extremely long transient lifetime. Historically the possibility of such transient raised the question of whether asymptotic attractors are relevant to turbulence. Here we investigate the phenomenon of noise-induced super-persistent chaotic transients. In particular, we construct a prototype model based on random maps to illustrate this phenomenon. We then approximate the model by stochastic differential equations and derive the scaling laws for the transient lifetime versus the noise amplitude epsilon for both the subcritical (p< p(c)) and the supercritical (p> p(c)) cases. Our results are the following. In the subcritical case where a chaotic attractor exists in the absence of noise, noise-induced transients can be more persistent in the following sense of double-exponential and algebraic scaling: tau approximately exp[K0 exp(K1epsilon(-gamma))] for small noise amplitude epsilon, where K0 >0 , K1 >0, and gamma>0 are constants. The longevity of the transient lifetime in this case is striking. For the supercritical case where there is already a super-persistent chaotic transient, noise can significantly reduce the transient lifetime. These results add to the understanding of the interplay between random and deterministic chaotic dynamics with surprising physical implications.