Several applications, like malicious URL detection and web spam de- tection, require anomaly or outlier detection on very high-dimensional data. In such cases anomalous data is hard to find but normal data is easily available. As such it is increasingly common to use a one- class classifier (OCC). Unfortunately, most OCC algorithms cannot scale to datasets with extremely high dimensions. In this paper, we present Fast Random projection-based One-Class Classification (FROCC), an extremely efficient, scalable and easily parallelizable method for one-class classification with provable theoretical guar- antees. Our method is based on the simple idea of transforming the training data by projecting it onto a set of random unit vec- tors that are chosen uniformly and independently from the unit sphere, and bounding the regions based on separation of the data. FROCC can be naturally extended with kernels. We theoretically prove that FROCC generalizes well in the sense that it is stable and has low bias. We then develop a fast scalable approximation of FROCC using vectorization, exploiting data sparsity and parallelism to develop a new implementation called ParDFROCC. ParDFROCC achieves upto 2 percent points better ROC than the next best baseline, with upto 12× speedup in training and test times over a range of state-of-the-art benchmarks for the OCC task.