: Navigation system for high-speed trains is necessary for increased operational safety and efficiency, new services for customers, and low maintenance cost. This paper proposes a high accuracy navigation system for high-speed trains based on a sensor fusion algorithm, with non-holonomic constraints, for multiple sensors, such as accelerometers, gyroscopes, tachometers, Doppler radar, differential GPS, and RFID, and a map matching algorithm. In the proposed system, we consider the federated Kalman filter for sensor fusion, where local filters utilize filter models developed for various sensor types. Especially, the local Kalman filter for RFID positioning, that is detected at irregular time intervals due to the varying train speed and RFID tag spacing, is developed to maintain high performance during GPS outage. In addition, an orthogonal projection map matching algorithm is developed to improve the performance of the proposed system. The performance of the proposed system is demonstrated with numerous simulations for a high-speed train in Korea. The simulation results are analyzed with respect to the existence of tunnel, RFID deployment spacing, RFID location uncertainty, and DGPS error.