This study is focused on addressing the problem of delayed measurements and contaminated Gaussian distributions in navigation systems, which both have a tremendous deleterious effect on the performance of the traditional Kalman filtering. We propose a non-linear, multiple-step, randomly delayed, robust filter, referred to as the multiple-step, randomly delayed, dynamic-covariance-scaling cubature Kalman filter (MRD-DCSCKF). First, Bernoulli random variables are adopted to describe the measurement system in the presence of multiple-step random delays. Then, the MRD-DCSCKF uses the framework of the multiple-step randomly delayed filter, based on a state-augmentation approach, to address the problem of delayed measurements. Meanwhile, it depends on a dynamic-covariance-scaling (DCS) robust kernel to reject the outliers in the measurements. Consequently, the proposed filter can simultaneously address the problem of delayed measurements and inherit the virtue of robustness of the DCS kernel function. The MRD-DCSCKF has been applied to vision-based spacecraft-relative navigation simulations, where quaternions are adopted to represent spacecraft’s attitude kinematics, and the attitude update is completed with quaternions and generalized Rodrigues parameters. Monte Carlo simulations have illustrated that MRD-DCSCKF is superior to other well-known algorithms by providing high-accuracy position and attitude estimations in an environment with different delay probabilities and/or different outlier-contamination probabilities. Therefore, the proposed filter is robust to delayed measurements and can suppress outliers.