In order to improve the accuracy of short-term PM2.5 prediction, we proposed a new hybrid solution that combines several machine learning techniques. Firstly, a set of phase space features are obtained from PM2.5 historical data based on PSR technique and combined with numerical weather prediction (NWP) data to construct a pool of candidate features. Secondly, the optimal feature subset is selected and input to the multi-step ahead prediction model based on the RReliefF feature selection algorithm. Then, K-means clustering is used to divide the input instances into a number of subsets to train ANFIS. Finally, the particle swarm optimization (PSO) algorithm is used to optimize the ANFIS network’s parameters. In order to verify the effectiveness of the proposed method, two benchmark models (PSR-FS, PCA-FS) were established to compare with the hybrid model. The experimental results showed that the hybrid solution obtained the best prediction performance in short-term PM2.5 prediction.