As a classic positioning algorithm with a simple principle and low computational complexity, the trilateration positioning algorithm utilizes the coordinates of three anchor nodes to determine the position of an unknown node, which is widely applied in various positioning scenes. However, due to the environmental noise, environmental interference, the distance estimation error, the uncertainty of anchor nodes’ coordinates, and other negative factors, the positioning error increases significantly. For this problem, we propose a new trilateration algorithm based on the combination and K-Means clustering to effectively remove the positioning results with significant errors in this paper, which makes full use of the position and distance information of the anchor nodes in the area. In this method, after analyzing the factors affecting the optimization of the trilateration and selecting optimal parameters, we carry out experiments to verify the effectiveness and feasibility of the proposed algorithm. We also compare the positioning accuracy and positioning efficiency of the proposed algorithm with those of other algorithms in different environments. According to the comparison of the least-squares method, the maximum likelihood method, the classical trilateration and the proposed trilateration, the results of the experiments show that the proposed trilateration algorithm performs well in the positioning accuracy and efficiency in both light-of-sight (LOS) and non-light-of-sight (NLOS) environments. Then, we test our approach in three realistic environments, i.e., indoor, outdoor and hall. The experimental results show that when there are few available anchor nodes, the proposed localization method reduces the mean distance error compared with the classical trilateration, the least-squares method, and the maximum likelihood.