A relativistic theory of modified gravity has been recently proposed by Bekenstein. The tensor field in Einstein's 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 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. The impact on galaxy distributions and the cosmic microwave background is calculated in detail. We show that it is possible to reproduce observations of the CMBR and LSS.