Railway tracks are one of the most important assets in rail transport that are subject to very high stresses and have to be made of very high-quality steel alloy. The dominant form of track degradation is Rolling Contact Fatigue (RCF) which occurs mainly due to cyclic loading. If RCF is not controlled by maintenance operations, it will result in intensive correction works, service disruption, and even train derailment. In order to reduce such negative consequences and improve the quality of transport services, the railway organizations are moving towards using prognostic analytics approaches for the optimisation of maintenance and repair actions. In this paper, we investigate a cost-optimal prognostic maintenance policy for a railway track system by incorporating RCF data. The mechanism of RCF is analyzed by means of Finite Element Analysis (FEA) and the fatigue propagation behavior is described by the Paris-Erdogan power law function. The length of the cracks over time is also modelled by a stochastic gamma process and its parameters are estimated using the Maximum Likelihood Estimation (MLE) method. An optimization model is proposed to determine fixed time interval and/or Million Gross Tons (MGT) achieving the best possible balance between non-destructive tests and emergency maintenance. The proposed model is applied to support the maintenance decision-making for a conventional rail track system 60E1 in steel grade R350HT. The results show that the use of the proposed prognostic maintenance allows a significant reduction of the costs compared to the strategy when maintenance is conducted on an as-needed basis.