Online fraud poses a relatively new threat to the revenues of companies. A way to detect and prevent fraudulent behavior is with the use of specific machine learning (ML) techniques. These anomaly detection techniques have been thoroughly studied, but the level of employment is not as high. The airline industry suffers from fraud by parties such as online travel agencies (OTAs). These agencies are commissioned by an airline carrier to sell its travel tickets. Through policy violations, they can illegitimately claim some of the airline’s revenue by offering cheaper fares to customers. This research applies several anomaly detection techniques to detect fraudulent behavior by OTAs and assesses their strengths and weaknesses. Since the data is not labeled, it is not known whether fraud has actually occurred. Therefore, unsupervised ML is used. The contributions of this paper are, firstly, to show how to shape the online booking data and how to engineer new and relevant features. Secondly, this research includes a case study in which domain experts evaluate the detection performance of the considered ML methods by classifying a set of 75 bookings. According to the experts’ analysis, the techniques are able to discover previously unknown fraudulent bookings, which will not have been found otherwise. This demonstrates that anomaly detection is a valuable tool for the airline industry to discover fraudulent behavior.