This paper investigates the design of accelerated life test (ALT) sampling plans under progressive Type II interval censoring with random removals. For ALT sampling plans with two over-stress levels, the optimal stress levels and the allocation proportions to them are obtained by minimizing the asymptotic generalized variance of the maximum likelihood estimation of model parameters. The required sample size and the acceptability constant which satisfy given levels of producer’s risk and consumer’s risk are found. ALT sampling plans with three over-stress levels are also considered under some specific settings. The properties of the derived ALT sampling plans under different parameter values are investigated by a numerical study. Some interesting patterns, which can provide useful insight to practitioners in related areas, are found. The true acceptance probabilities are computed using a Monte Carlo simulation and the results show that the accuracy of the derived ALT sampling plans is satisfactory. A numerical example is also provided for illustrative purpose.