We show that M-theory admits a supersymmetric compactification to the Godel universe of the form Godel3 x S2 x CY3. We interpret this geometry as coming from the backreaction of M2-branes wrapping the S2 in an AdS3 x S2 x CY3 flux compactification. In the black hole deconstruction proposal similar states give rise to the entropy of a D4-D0 black hole. The system is effectively described by a three-dimensional theory consisting of an axion-dilaton coupled to gravity with a negative cosmological constant. Other embeddings of the three-dimensional theory imply similar supersymmetric Godel compactifications of type IIA/IIB string theory and F-theory.