In the past few decades, several models have predicted an energy dependence of the speed of light in the context of quantum gravity. For cosmological sources such as active galaxies, this minuscule effect can add up to measurable photon-energy dependent time lags. In this Letter a search for such time lags during the High Energy Stereoscopic System observations of the exceptional very high energy flare of the active galaxy PKS 2155-304 on 28 July 2006 is presented. Since no significant time lag is found, lower limits on the energy scale of speed of light modifications are derived.