Over the last decade, a novel nondestructive evaluation (NDE) method based on the application of highly nonlinear solitary waves has emerged. The method is based on the actuation and detection of solitary waves propagating along a medium made of uniform spherical particles, the last of which is in contact with the material to be assessed noninvasively. The hypothesis is that the dynamic interaction between the wave and the material/structure to be inspected is dependent upon the condition of the material/structure. The study presented in this paper aims at designing and developing the NDE framework for the detection of localized corrosion in metals. In particular, this paper presents a numerical investigation of the interaction of highly nonlinear solitary waves with plates in pristine and corroded conditions. A coupled discrete/finite element model is used to predict the time of flight and the relative amplitudes of the reflected solitary waves as localized corrosion progresses in the plate. The sensitivity of the method is quantified in terms of different parameters such as plate thickness, chain length, and particles' mechanical and geometric properties. It is found that the sensitivity, i.e. the ability to detect corrosion at earlier stages, of this novel NDE technique is inversely proportional to the plate thickness and is proportional to the diameter and the stiffness of the particles. In the future, the findings of this study can be used to optimize the design of solitary wave transducers, which are devices that can be used to trigger, sustain, and detect the propagation of the solitary waves and their interaction with the structure of interest.