China is a big country of aquatic products production and consumption. Due to the great quality and price gap between the fish products from closely related species, the phenomena of adulteration and mislabeling of fish products have occurred frequently, which greatly encroached on the consumers’ legitimate rights. Therefore, it is important to realize a rapid detection of the variety and quality of fish products. Laser-induced breakdown spectroscopy (LIBS) utilizes a pulsed laser to ablate the sample surface and generate a laser-induced plasma. Then the emission spectrum from the plasma is used for a qualitative or quantitative analysis of the elemental components of the sample. LIBS has shown great potential to be used in the food fast detection field with no or minimal sample preparation, multi-elemental analysis, and rapid detection capabilities. This paper applied LIBS combined with the random forest (RF) method to rapidly identify different fish products. Firstly, six fish samples were prepared into pellets, and the LIBS spectra were acquired using a handheld LIBS device. Clear spectral lines of C, Mg, CN, Ca, Na, H, K and O can be observed in the hand held-LIBS spectrum. After normalization of the raw spectral data, the principal component analysis (PCA) was used for clustering, and it was shown that the salt water fishes and freshwater fishes could be distinguished. In contrast, the different types inside the saltwater fishes or freshwater fishes can hardly be distinguished, indicating a limited capability of PCA method for the classification. Then, a nonlinear RF method was used to build the classification model. After optimizing the model parameters, including the decision tree number and the maximum depth, the RF model got an overall classification accuracy of 90%. In order to further improve the classification accuracy and efficiency, a feature selection method was performed by utilizing the variable importance of the RF model. It was shown that after feature selection, the classification accuracy was improved to 94.44%, and the number of input variables of the RF model was reduced from 23 431 to 597. Thus the computing time of the RF model was clearly reduced. The obtained results suggested that the RF model combined with variable importance selection can successfully distinguish the weak LIBS signals which have high impacts on the classification and eliminate the interferences from the spectral noise, background and other redundant variables, and therefore have a good classification accuracy and efficiency. This work proves the feasibility of handheld LIBS combined with machine learning for the application of rapid fish product identification in the market.