Homogeneous relaxation is a ubiquitous phenomenon in semiclassical kinetic theories where the quasiparticles are distributed uniformly in space, and the equilibration involves only their velocity distribution. For such solutions, the hydrodynamic variables remain constant. We construct asymptotically AdS solutions of Einstein's gravity dual to such processes at strong coupling, perturbatively in the amplitude expansion, where the expansion parameter is the ratio of the amplitude of the nonhydrodynamic shear-stress tensor to the pressure. At each order, we sum over all time derivatives through exact recursion relations. We argue that the metric has a regular future horizon, order by order in the amplitude expansion, provided the shear-stress tensor follows an equation of motion. At the linear order, this equation of motion implies that the metric perturbations are composed of zero wavelength quasinormal modes. Our method allows us to calculate the nonlinear corrections to this equation perturbatively in the amplitude expansion. We thus derive a special case of our previous conjecture on the regularity condition on the boundary stress tensor that endows the bulk metric with a regular future horizon, and also refine it further. We also propose a new outlook for heavy-ion phenomenology at RHIC and ALICE. © 2011 American Physical Society.