This paper proposes a practical and realistic method to establish an optimal lifetime maintenance strategy for deteriorating bridges by considering the life-cycle performance as well as the life-cycle cost. The proposed method offers a set of optimal tradeoff maintenance scenarios among other conflicting objectives, such as minimizing cost and maximizing performance. A genetic algorithm is used to generate a set of maintenance scenarios that is a multi-objective combinatorial optimization problem related to the lifetime performance and the life-cycle cost as separate objective functions. A computer program, which generates optimal maintenance scenarios, was developed based on the proposed method using the life-cycle costs and the performance of bridges. The subordinate relation between bridge members has been considered to decide optimal maintenance sequence and a corresponding algorithm has been implemented into the program. The developed program has been used to present a procedure for finding an optimal maintenance scenario for steel-girder bridges on the Korean National Road. Through this bridge maintenance scenario analysis, it is expected that the developed method and program can be effectively used to allow bridge managers an optimal maintenance strategy satisfying various constraints and requirements.