Fatigue cracks and bolt looseness are the main damage forms of steel towers, such as relay towers and transmission towers. Under time-domain loads, these damages have time-domain nonlinear characteristics such as variable stiffness. To solve the time-domain nonlinear damage detection problem, a damage detection method based on the relative entropy of the autoregressive time-domain model is proposed. First, the autoregressive model and the basic theory of model order determination and parameter estimation are described. Then, the time-domain nonlinear characteristic of structural damage is introduced, and the three autoregressive residuals formed in the undamaged basic state and the damage state are given. In addition, the relative entropy of the probability distribution of the residual series is analyzed. On this basis, the damage detection index based on the relative entropy of the autoregressive time-domain model is derived. Finally, the numerical simulation of the eight-layer shear structure and the damage detection experimental study of the relay tower model are conducted. The results show that the relative entropy index value of the autoregressive time-domain model at the damage location is more than 22. 9% higher than the traditional second-order variance index value for the rod nonlinear damage of the relay tower. For the bolt loosening nonlinear damage, the relative entropy index value of the autoregressive time-domain model at the damage location is more than 12. 7% higher than the traditional second-order variance index value.