We investigate supergravity models in which the lightest supersymmetric particle (LSP) is a stable gravitino. We assume that the next-lightest supersymmetric particle (NLSP) freezes out with its thermal relic density before decaying to the gravitino at time tsimilar to10(4)-10(8)s. In contrast to studies that assume a fixed gravitino relic density, the thermal relic density assumption implies upper, not lower, bounds on superpartner masses, with important implications for particle colliders. We consider slepton, sneutrino, and neutralino NLSPs, and determine what superpartner masses are viable in all of these cases, applying cosmic microwave background (CMB) and electromagnetic and hadronic big bang nucleosynthesis (BBN) constraints to the leading two- and three-body NLSP decays. Hadronic constraints have been neglected previously, but we find that they provide the most stringent constraints in much of the natural parameter space. We then discuss the collider phenomenology of supergravity with a gravitino LSP. We find that colliders may provide important insights to clarify BBN and the thermal history of the Universe below temperatures around 10 GeV and may even provide precise measurements of the gravitino's mass and couplings.