We present a joint theory-experiment study on ultrafast photoluminescence from photoexcited graphene. Based on a microscopic theory, we reveal two distinct mechanisms behind the occurring photoluminescence: Besides the well-known incoherent contribution driven by non-equilibrium carrier occupations, we found a coherent part that spectrally shifts with the excitation energy. In our experiments, we demonstrate for the first time the predicted appearance and spectral shift of the coherent photoluminescence.