Background <p>Cluster randomized trials, which often enroll a small number of clusters, can benefit from constrained randomization, selecting a final randomization scheme from a set of known, balanced randomizations. Previous literature has addressed the suitability of adjusting the analysis for the covariates that were balanced in the design phase when the outcome is continuous or binary. Here we extended this work to time-to-event outcomes by comparing two model-based tests and a newly derived permutation test. A current cluster randomized trial of vector control for the prevention of mosquito-borne disease in children in Mexico is used as a motivating example.</p> Methods <p>We assessed type I error rates and power between simple randomization and constrained randomization using both prognostic and non-prognostic covariates via a simulation study. We compared the performance of a semi-parametric Cox proportional hazards model with robust variance, a mixed effects Cox model, and a permutation test utilizing deviance residuals.</p> Results <p>The permutation test generally maintained nominal type I error—with the exception of the unadjusted analysis for constrained randomization—and also provided power comparable to the two Cox model-based tests. The model-based tests had inflated type I error when there were very few clusters per trial arm. All three methods performed well when there were 25 clusters per trial arm, as in the case of the motivating example.</p> Conclusion <p>For time-to-event outcomes, covariate-constrained randomization was shown to improve power relative to simple randomization. The permutation test developed here was more robust to inflation of type I error compared to model-based tests. Gaining power by adjusting for covariates in the analysis phase was largely dependent on the number of clusters per trial arm.</p>