We examine the LHC phenomenology of quantum black holes in models of TeV gravity. By quantum black holes we mean black holes of the smallest masses and entropies, far from the semiclassical regime. These black holes are formed and decay over short distances, and typically carry SU(3) color charges inherited from their parton progenitors. Based on a few minimal assumptions, such as gauge invariance, we identify interesting signatures for quantum black hole decay such as 2 jets, jet + hard photon, jet + missing energy and jet + charged lepton, which should be readily visible above background. The detailed phenomenology depends heavily on whether one requires a Lorentz invariant, low-energy effective field theory description of black hole processes.