Extreme learning machine (ELM) is a kind of random projection-based neural networks, whose advantages are fast training speed and high generalization. However, three issues can be improved in ELM: (1) the calculation of output weights takes O L2N time (with N training samples and L hidden nodes), which is relatively slow to train a model for large N and L; (2) the manual tuning of L is tedious, exhaustive and time-consuming; (3) the redundant or irrelevant information in the hidden layer may cause overfitting and may hinder high generalization. Inspired from compressive sensing theory, we propose an efficient ELM via very sparse random projection (VSRP) called VSRP-ELM for training with large N and L. The proposed VSRP-ELM adds a novel compression layer between the hidden layer and output layer, which compresses the dimension of the hidden layer from N×L to N×k (where k < L) under projection with random sparse-Bernoulli matrix. The advantages of VSRP-ELM are (1) faster training time O k2N , k < L, is obtained for large L; (2) the tuning time of L can be significantly reduced by initializing a large L, and then shrunk to k using just a few trials, while maintaining a comparable result of the original model accuracy; (3) higher generalization may be benefited from the cleaning of redundant or irrelevant information through VSRP. From the experimental results, the proposed VSRP-ELM can speed ELM up to 7 times, while the accuracy can be improved up to 6%.