We perform a new test of Einstein's Equivalence Principle which, for the first time, extends to very early cosmological epochs (we have studied its validity in 80% of the history of the Universe). The Einstein Equivalence Principle is essential for generalizing physical laws in the presence of gravity. Our test of the Equivalence Principle is based on one of Einstein's classical predictions: the gravitational redshift of photons. This test has been accurately put into practice in our Solar System and in some stars in our Galaxy (e.g. Sirius B). However, so far it has not been applied to cosmological distances (i.e. in earlier epochs of the Universe). Our test consists in measuring the redshift of photons emitted by matter spiraling around the supermassive black hole at the center of the quasars. Specifically, we measure this redshift in ultraviolet emission lines produced by iron atoms confined in a region very close to the central black hole. Our results indicate that, with an accuracy of 13%, there is no significant change in the predictions of Einstein's Equivalence Principle between the young Universe (approximately 2200 million years after the Big Bang) and the present Universe (13800 million years after the Big Bang).