The objective of this study is to explore the feasibility of using ultrasonic pulse wave measurements as an early detection method for corrosion-induced concrete damages. A series of experiments are conducted using concrete cube specimens, at a size of 200 mm, with a reinforcing steel bar (rebar) embedded in the center. The main variables include the water-to-cement ratio of the concrete (0.4, 0.5, and 0.6), the diameter of the rebar (10 mm, 13 mm, 19 mm, and 22 mm), and the corrosion level (ranging from 0% to 20% depending on rebar diameter). The impressed current technique is used to accelerate corrosion of rebars in concrete immersed in a 3% NaCl solution. Ultrasonic pulse waves are collected from the concrete specimens using a pair of 50 kHz P-wave transducers in the through-transmission configuration before and after the accelerated corrosion test. Deep learning techniques, specifically three recurrent neural network (RNN) models (long short-term memory, gated recurrent unit, and bidirectional long short-term memory), are utilized to develop a classification model for early detection of concrete damage due to rebar corrosion. The performance of the RNN models is compared to conventional ultrasonic testing parameters, namely ultrasonic pulse velocity and signal consistency. The results demonstrate that the RNN method outperforms the other two methods. Among the RNN methods, the bidirectional long short-term memory RNN model had the best performance, achieving an accuracy of 74% and a Cohen’s kappa coefficient of 0.48. This study establishes the potentiality of utilizing deep learning of ultrasonic pulse waves with RNN models for early detection of concrete damage associated with steel corrosion.