The common intuition among the ecologists of the midtwentieth century was that large ecosystems should bemore stable than those with a smaller number of species. This view was challenged by Robert May, who found a stability bound for randomly assembled ecosystems; they become unstable for a sufficiently large number of species. In the present work, we show that May's bound greatly changes when the past population densities of a species affect its own current density. This is a common feature in real systems, where the effects of species' interactions may appear after a time lag rather than instantaneously. The local stability of these models with self-interaction is described by bounds, which we characterize in the parameter space. We find a critical delay curve that separates the region of stability fromthat of instability, and correspondingly, we identify a critical frequency curve that provides the characteristic frequencies of a system at the instability threshold. Finally, we calculate analytically the distributions of eigenvalues that generalizeWigner's aswell asGirko's laws. Interestingly, we find that, for sufficiently large delays, the eigenvalues of a randomly coupled system are complex even when the interactions are symmetric.