In this paper, a stochastic dynamic programming (SDP) based optimization model is formulated for the equipment replacement optimization (ERO) problem that can explicitly account for the uncertainty in vehicle utilization. The Bellman approach is developed and implemented to solving the ERO SDP problem. Particular attention is paid to the SDP state-space growth and special scenario reduction techniques are developed to resolve the “curse of dimensionality” issue that is inherent to the dynamic programming method to ensure that the computer memory and solution computational time required will not increase exponentially with the increase in time horizon. SDP software computer implementation techniques, functionalities and the Graphical User Interfaces (GUI) are discussed. The developed SDP-based ERO software is tested and validated using the current Texas Department of Transportation (TxDOT) vehicle fleet data. Comprehensive numerical results, such as statistical analyses, the software computational time and solution quality, are described and substantial cost-savings have been estimated by using this ERO software. Finally, future research directions are also suggested.