We prove that the solution to a parabolic integro-differential equation with a gradient dependence that satisfies a critical power growth becomes immediately Holder continuous. We also obtain some results in the supercritical case.