Nowadays Fiber Reinforced Cementitious Matrix (FRCM) composites are considered as a primary strengthening technique for reinforced concrete and masonry constructions, especially for historic buildings. Historic structures exhibit a pronounced seismic vulnerability, entailing the risk of losing important parts of the world's cultural heritage. A vast literature is available on issues like the interactions, the adhesion, and the delamination strength between FRCM composites and masonry. However, much fewer studies concern the detection of possible defects in the adhesion between FRCM and masonry, formed during the application of the reinforcement or during the service life of the construction, for example, from exceptional loads like earthquake, fire, etc. These defects can strongly undermine the effectiveness of the strengthening intervention, and thus the structural safety of the reinforced construction. Here, an innovative nonlinear ultrasonic technique called Side-band Peak Count (SPC) is proposed for detecting defects in the adhesion between FRCM composite layers and masonry substrates. The SPC technique reprocesses the results of the ultrasonic guided wave tests by relating the level of the non-linearity of the ultrasonic response due to the damage, to the appearance of additional secondary components in the spectrum of the received signal. Experiments are conducted on masonry tuff specimens reinforced with FRCM mortars and basalt fibers grid embedment. Specimens with known artificial defects are tested. Defects are fabricated both at the FRCM-tuff interface and within the FRCM layer, i.e., at the interface mortar-reinforcement fiber grid. The effectiveness of the proposed approach is investigated and discussed.