A relativistic theory of modified gravity has been recently proposed by Bekenstein. The tensor field in Einsteins theory of gravity is replaced by a scalar, a vector, and a tensor field which interact in such a way to give Modified Newtonian Dynamics (MOND) in the weak-field non-relativistic limit. We study the evolution of the universe in such a theory, identifying its key properties and comparing it with the standard cosmology obtained in Einstein gravity. The evolution of the scalar field is akin to that of tracker quintessence fields. We expand the theory to linear order to find the evolution of perturbations on large scales. The impact on galaxy distributions and the cosmic microwave background is calculated in detail. We show that it may be possible to reproduce observations of the cosmic microwave background and galaxy distributions with Bekensteins theory of MOND.