Based on the Kalker’s three-dimensional elastic bodies rolling contact theory and combined with the wheel-rail non-flat contact geometric relationship, the modified equation of the influence coefficient implemented in the minimum complementary energy equation was presented. Considering the interaction between the normal and the shear effects of wheel-rail non-flat contact, the minimum complementary energy equation was discretized. The solution of the discretized equation was transformed into a nonlinear programming problem with the target of the minimum of the total complementary energy, and the algorithm for solving the problem was proposed. The accuracy of the algorithm was validated with a finite element simulation. Lastly, the wheel-rail non-flat contact characteristics under different worn rail conditions were studied and the results show that, under the conditions of different wears and same lateral displacements, with the wear increasing, the wheel-rail contact occurred in the gauge corner changes from a two-point contact to a conformal contact, the corresponding maximum stress decreases, the contact patch becomes narrow and long, and the contact area increases.