We study the critical behavior of the ferromagnetic Ising model on random trees as well as so-called locally tree-like random graphs. We pay special attention to trees and graphs with a power-law offspring or degree distribution whose tail behavior is characterized by its power-law exponent t > 2. We show that the critical inverse temperature of the Ising model equals the hyperbolic arctangent of the reciprocal of the mean offspring or mean forward degree distribution. In particular, the critical inverse temperature equals zero when t¿(2,3] where this mean equals infinity. We further study the critical exponents d, ß and ¿, describing how the (root) magnetization behaves close to criticality. We rigorously identify these critical exponents and show that they take the values as predicted by Dorogovstev et al. (Phys Rev E 66:016104, 2002) and Leone et al. (Eur Phys J B 28:191–197, 2002). These values depend on the power-law exponent t, taking the same values as the mean-field Curie-Weiss model (Exactly solved models in statistical mechanics, Academic Press, London, 1982) for t > 5, but different values for t¿(3,5) .