The durability of the interface between NSM FRP and concrete under freeze-thawing cycles was examined. The pull-out tests were conducted to investigate the influence of freeze-thawing cycles on the bond performance between NSM FRP and concrete with normal strength, high strength, or additional frost resistance. The mechanism of the bond degradation between NSM FRP and concrete under the freeze-thawing cycles was also discussed. Moreover, the influences of the distance between concrete edge and groove (edge distance) and the thickness of epoxy adhesive on the bond durability of the NSM FRP were studied. The test results show that freeze-thawing cycling resulted in the strength deterioration of ordinary concrete, while the high strength concrete and the concrete with frost resistance showed no significant deterioration under freeze-thawing cycles. Freeze-thawing cycling also caused the transformation of failure mode and the relatively significant decrease in bond capacity for specimens using ordinary concrete. Nevertheless, it had no substantial impact on the bond performance of specimens made by concrete with high strength or frost resistance. This result indicates that the bond deterioration of NSM FRP under freeze-thawing cycles was caused by low strength of concrete. Moreover, the decrease of edge distance resulted in cone-shape cracks at the loading end. When the thickness of epoxy adhesive was reduced, the bond strength degradation induced by freeze-thawing cycles was more significant compared with that of specimens with thicker epoxy adhesive.