The past decade has witnessed the rapid growth of online auctions. However, the low cost and anonymity in joining online auctions provided an easy path for fraudsters. The simple binary reputation system promoted by the auction site is clearly not enough to protect consumers from fraud. In view of this, many fraud detection methods have been proposed. Nevertheless, there are still many weaknesses needed to be improved. To help secure the online trading environment, this study aims at developing more effective methods to identify the fraudsters in online auctions. First, a novel selection method is proposed for deriving a concise attribute set used to build efficient detection models, which allow a reduction in detection costs while improving detection accuracy. In addition, a two-stage detection procedure is proposed wherein multiple mutual-complement models are combined for promoting overall detection accuracy. To evaluate the proposed methods, actual auction transaction histories were collected for testing. The experimental results show that these methods can outperform those in the previous work.