Coalescing binary black holes experience a ``kick due to anisotropic emission of gravitational waves with an amplitude as great as 200$ km/s. We examine the orbital evolution of black holes that have been kicked from the centers of triaxial galaxies. Time scales for orbital decay are generally longer in triaxial galaxies than in equivalent spherical galaxies, since a kicked black hole does not return directly through the dense center where the dynamical friction force is highest. We evaluate this effect by constructing self-consistent triaxial models and integrating the trajectories of massive particles after they are ejected from the center; the dynamical friction force is computed directly from the velocity dispersion tensor of the self-consistent model. We find return times that are several times longer than in a spherical galaxy with the same radial density profile, particularly in galaxy models with dense centers, implying a substantially grea