Scenarios with gravitino dark matter face potential cosmological problems induced by the presence of the Next-to-Lightest Supersymmetric Particle (NLSP) at the time of Big Bang Nucleosynthesis (BBN). A very simple solution to avoid all these problems consists on assuming that R-parity is slightly violated, since in this case the NLSP decays well before the onset of BBN. Remarkably, even if the gravitino is no longer stable in this scenario, it still constitutes a very promising dark matter candidate. In this talk we review the motivations for this scenario and we present a model that naturally generates R-parity breaking parameters of the right size to produce a consistent thermal history of the Universe, while satisfying at the same time all the laboratory and cosmological bounds on R-parity breaking. We also discuss possible signatures of this scenario at gamma ray observatories and at colliders.