We present a set of N-body simulations of a class of models in which an unstable dark matter particle decays into a stable non-interacting dark matter particle, with decay lifetime comparable to the Hubble time. We study the effects of the kinematic recoil velocity received by the stable dark matter on the structures of dark matter halos ranging from galaxy-cluster to Milky Way mass scales. For Milky Way-mass halos, we use high-resolution, zoom-in simulations to explore the effects of decays on Galactic substructure. In general, halos with circular velocities comparable to the magnitude of kick velocity are most strongly affected by decays. We show that decaying dark matter models with lifetimes comparable to Hubble time and recoil speeds about 20-40 km/s can significantly reduce both the abundance of Galactic subhalos and the internal densities of the subhalos. We also compare subhalo circular velocity profiles with observational constraints on the Milky Way dwarf satellite galaxies. Interestingly, we find that decaying dark matter models that do not violate current astrophysical constraints, can significantly mitigate both the well-documented "missing satellites problem" and the more recent "too big to fail problem" associated with the abundances and densities of Local Group dwarf satellite galaxies. A relatively unique feature of late decaying dark matter models is that they predict significant evolution of halos as a function of time. This is an important consideration because at high redshifts, prior to decays, decaying models exhibit the same sequence of structure formation as cold dark matter. We conclude that models of decaying dark matter make predictions that are relevant for the interpretation of observations of small galaxies in the Local Group and can be tested or constrained by the kinematics of Local Group dwarf galaxies as well as by forthcoming large-scale surveys.