We address issues related to establishing a defender's reputation in anomaly detection against two types of attackers: 1) smart insiders, who learn from historic attacks and adapt their strategies to avoid detection/punishment, and 2) naïve attackers, who blindly launch their attacks without knowledge of the history. In this paper, we propose two novel algorithms for reputation establishment--one for systems solely consisting of smart insiders and the other for systems in which both smart insiders and naïve attackers are present. The theoretical analysis and performance evaluation show that our reputation-establishment algorithms can significantly improve the performance of anomaly detection against insider attacks in terms of the tradeoff between detection and false positives.