Wireless sensor networks (WSNs) are often deployed in harsh and unattended environments, which may cause the generation of abnormal or low quality data. The inaccurate and unreliable sensor data may increase generation of false alarms and erroneous decisions, so it’s very important to detect outliers in sensor data efficiently and accurately to ensure sound scientific decision-making. In this paper, an outlier detection algorithm (TSVDD) using model selection-based support vector data description (SVDD) is proposed. Firstly, the Toeplitz matrix random feature mapping is used to reduce the time and space complexity of outlier detection. Secondly, a novel model selection strategy is realized to keep the algorithm stable under the low feature dimensions, this strategy can select a relatively optimal decision model and avoid both under-fitting and overfitting phenomena. The simulation results on SensorScope and IBRL datasets demonstrate that, TSVDD achieves higher accuracy and lower time complexity for outlier detection in WSNs compared with existing methods.