This study investigates the punching shear strength of concrete bridge decks strengthened with various fiber reinforced polymer (FRP) materials, carbon fiber sheet (CFS), glass fiber sheet (GFS) and carbon fiber grid (CFG). This study performed fatigue loading tests on the strengthened bridge decks with different fatigue loading levels. Based on the experimental results, a damage index was determined considering the damage mechanics and was applied to the plastic punching shear strength model for the evaluation of the punching shear strength with respect to the number of fatigue loading cycles. The developed model seems to successfully estimate the punching shear strength of damaged bridge decks with sufficient reliability. It is anticipated, therefore, that the developed model may help improving the design of strengthening of damaged bridge deck panels.