Steel-concrete composite structures are prevalent in civil engineering, however, due to the temperature variation and fatigue loading, the interface between the steel tube and the core concrete is susceptible to various types of damage, including cracking, delamination, and debonding. Accurate localization of interface damage is crucial to ensure the safety of steel-concrete composite structures. The time-reversal (TR) method is commonly used in nondestructive testing for localizing structural linear damage due to its temporal and spatial focusing characteristics. However, the damage in the steel-concrete interface exhibits complex mechanical behavior and results in localization errors with the traditional TR method. To address this challenge, combined with the advantages of the VAM method, this paper proposes a nonlinear ultrasonic TR method to improve the accuracy of the TR method. This novel approach involves simultaneously exciting low-frequency (LF) and high-frequency (HF) signals using only one lead zirconate titanate (PZT) transducer, extracting the first-order modulation sideband signal, reversing and reemitting this signal, and utilizing the focused signal image to determine the location of damage at the interface. To validate the effectiveness of the proposed method, experiments were conducted on a concrete-filled steel tube with prefabricated interface damage to check its localization accuracy. The results clearly demonstrate an improvement in localization accuracy when using the proposed method compared to the conventional TR method. Specifically, the relative error in the coordinates for damage determined by the conventional TR method was significantly reduced from (25.89%, 18.82%) to (3.53%, 7.06%) with the proposed method. These findings underscore the superior performance of the proposed nonlinear ultrasonic TR method in localizing damage at the steel-concrete interface.