In this paper we propose novel randomized subspace methods to detect anomalies in Internet Protocol networks. Given a data matrix containing information about network traffic, the proposed approaches perform a normal-plus-anomalous matrix decomposition aided by random subspace techniques and subsequently detect traffic anomalies in the anomalous subspace using a statistical test. Experimental results demonstrate improvement over the traditional principal component analysis-based subspace methods in terms of robustness to noise and detection rate.