Locomotive reliability and spare parts availability are essential for maintaining railway operational performance and service continuity. However, previous studies have generally focused on component reliability or inventory management separately, with limited attention to integrating component reliability, fleet utilization, and spare parts demand characteristics into a unified framework for spare parts management. This study aims to address this gap by developing a reliability-based approach for identifying critical spare parts at Sidotopo Locomotive Depot, Operational Region 8 Surabaya, PT Kereta Api Indonesia (Persero). Historical maintenance and operational data were analyzed using Pareto analysis, material reconciliation, expert judgment, reliability analysis, fleet utilization assessment, and demand pattern classification. The analysis identified four critical components: AEP5, Victaulic 3.5", Flexible Hose, and Deadman. Weibull, Lognormal, and Exponential distributions were evaluated, and all components were found to follow the Weibull distribution, indicating wear-out failure behavior. At 1,008 operating hours, AEP5 exhibited the highest reliability, whereas Flexible Hose showed the lowest. Demand analysis classified AEP5 and Flexible Hose as intermittent demand, while Victaulic 3.5" and Deadman were categorized as lumpy demand. Fleet utilization analysis further revealed differences in component operating performance, providing additional insight into replacement priorities. The findings demonstrate that integrating reliability, fleet utilization, and demand characteristics provides a comprehensive basis for identifying critical spare parts, supporting maintenance planning, and improving inventory management in railway operations.