In this article, optimal accelerated degradation test plans under step-stress loading (step-ADT plans) are developed under the assumptions of destructive testing, a simple constant-rate relationship between the stress and the performance of a unit, and a cumulative exposure model for the effect of changing stress levels. As an optimization criterion, the asymptotic variance of the maximum likelihood estimator of the th quantile of the lifetime distribution at the use condition is adopted, and the stress levels, the proportion of units measured at each test point, and the stress changing time are optimally determined. Sensitivity analysis and sample size determination procedures are also illustrated with an example. Finally, the optimal step-ADT plan is compared with the corresponding optimal ADT plan under constant-stress loading in terms of statistical efficiency and the total amount of testing time. Computational results indicate that the proposed step-ADT plan is more economical in terms of testing time if only one test equipment can be employed.