We investigate the cosmological gravitino problem in gauge-mediated supersymmerry breaking models, where the gravitino becomes in general the lightest supersymmetric particle (LSP). In order to avoid the overclosure of the stable gravitino, the reheating temperature of inflation T-R should be low enough. Furthermore, if the gravitino moss is larger than about 100 MeV, the decay of the next-to-LSP (NLSP) into the gravitino may modify disastrously the abundances of the light elements predicted by the big-bang nucleosynthesis (BBN). We consider the case in which the lighter stau is the NLSP and derive cosmological constraints from the BBN on the stau NLSP decay. We obtain a lower bound on the mass of stau m(tau)over-bar-1, which is more stringent than the current experimental limit m(tau)over-bar-1 > 90 GeV for the gravitino mass region m(3/2) greater than or similar to 5 GeV. This lower bound, together with the overclosure constraint on the stable gravitino, gives an upper bound on T-R. We find that the reheating temperature can be as high as 10(9)-10(10) GeV for m(3/2) similar or equal to 5-100 GeV. (C) 2000 Published by Elsevier Science B.V.