Covariance matrices corresponding to samples of multivariate time series or spatial random fields have a block-Toeplitz structure that has a nested pattern. Also, non-lattice data samples yield nested covariance matrices, although they are no longer block-Toeplitz. The nested structure of such matrices facilitates the computation of their inverses, among other related quantities. Recursive algorithms, based upon this nested structure, are presented, yielding applications such as the simulation of vector time series, the evaluation of Gaussian likelihoods and Whittle likelihoods, the computation of spectral factorization, and the calculation of projections. Both multivariate time series applications and two-dimensional random fields applications are discussed, as well as applications to non-lattice data.