Asphalt mixture for railway substructure is subject to complex external conditions such as temperature and train cyclic load. Therefore, the excellent resistance to deformation, cracking, and fatigue failure of asphalt materials should be taken into consideration. In this research, based on the functional requirements of an asphalt railway substructure project in North China, a type of styrene-butadiene-styrene and crumb rubber composite modified asphalt (SBS+CR CMA) was proposed at first. Afterwards, several tests were performed to evaluate its thermal stability and fatigue resistance at the level of binder and mixture, respectively. Finally, compared with results of SBS+TPS (tough polystyrene) CMA and SBS MA, it was concluded that SBS+CR CMA showed much better low temperature cracking and fatigue resistance performances than the other two asphalts, although it had a weaker high temperature performance. Therefore, the proposed SBS+CR CMA was more suitable for this project and those applications in cold regions.