In the railway industry, re-adhesion control plays an important role in attenuating the slip occurrence due to the low adhesion condition in the wheel-rail interaction. Braking and traction forces depend on the normal force and adhesion coefficient at the wheel-rail contact area. Due to the restrictions on controlling normal force, the only way to increase the tractive or braking effect is to maximize the adhesion coefficient. Through efficient utilization of adhesion, it is also possible to avoid wheel-rail wear and minimize the energy consumption. The adhesion between wheel and rail is a highly nonlinear function of many parameters like environmental conditions, railway vehicle speed and slip velocity. To estimate these unknown parameters accurately is a very hard and competitive challenge. The robust adaptive control strategy presented in this paper is not only able to suppress the wheel slip in time, but also maximize the adhesion utilization performance after re-adhesion process even if the wheel-rail contact mechanism exhibits significant adhesion uncertainties and/or nonlinearities. Using an optimal slip velocity seeking algorithm, the proposed strategy provides a satisfactory slip velocity tracking ability, which was demonstrated able to realize the desired slip velocity without experiencing any instability problem. The control torque of the traction motor was regulated continuously to drive the railway vehicle in the neighborhood of the optimal adhesion point and guarantee the best traction capacity after re-adhesion process by making the railway vehicle operate away from the unstable region. The results obtained from the adaptive approach based on the second-order sliding mode observer have been confirmed through theoretical analysis and numerical simulation conducted in MATLAB and Simulink with a full traction model under various wheel-rail conditions.