This article makes a bridge between the theory of optimal auditing and the scoring methodology in an asymmetric information setting. Our application is meant for insurance claims fraud, but it can be applied to many other activities that use the scoring approach. Fraud signals are classified based on the degree to which they reveal an increasing probability of fraud. We show that the optimal auditing strategy takes the form of a “Red Flags Strategy” which consists in referring claims to a Special Investigative Unit (SIU) when certain fraud indicators are observed. The auditing policy acts as a deterrence device and we explain why it requires the commitment of the insurer and how it should affect the incentives of SIU staffs. The characterization of the optimal auditing strategy is robust to some degree of signal manipulation by defrauders as well as to the imperfect information of defrauders about the audit frequency. The model is calibrated with data from a large European insurance company. We show that it is possible to improve our results by separating different groups of insureds with different moral costs of fraud. Finally, our results indicate how the deterrence effect of the audit scheme can be taken into account and how it affects the optimal auditing strategy.