The 2016 Canada infrastructure report alarmed that more than 26% of Canada’s bridges are rated fair, poor, and very poor and an investment of $50 billion is required to replace all of these bridges. In the US, the situation is similar where the American Society of Civil Engineers (ASCE) report card graded bridges’ condition in 2017 as “C+” which refers to a mediocre condition that requires immediate attention. There is an overwhelming amount of maintenance and rehabilitation works to be done and selecting a suitable maintenance, repair or replacement (MRR) strategy is one of the most challenging tasks for decision makers. Limited budget and resources are making the decision making process much more challenging. The growing needs and limited resources to maintain the transportation networks have resulted in motivating transportation agencies to expand the amount of contracting they do through long term performance-based maintenance contracts or what is called Performance-Based Contracting (PBC). The main objective of this research is to develop short and long term optimized rehabilitation plans for bridge decks under PBC setting. In order to achieve this goal, performance modeling is established to measure current performance and predict future deterioration and improvements rates; moreover, associated MRR costs are estimated. A key performance measure, named condition reliability, is defined as an indicator to the structural condition or performance of the bridge component. Furthermore, an associated level of service (LOS) threshold is proposed. The output of this research is a decision- making tool for optimizing rehabilitation strategies with the lowest cost while maintaining a specified performance LOS. The principles of the proposed tool are demonstrated through a real case study of a bridge located in Quebec, Canada. The result of the proposed decision support tool is an optimized work program that satisfies the identified performance LOS and budget constraints. The model is expected to support decision makers to maintain their bridges using the PBC method.