For the nonlinear, non-Gaussian and high dynamic model in Strapdown Inertial Navigation System/Global Navigation Satellite System (SINS/GNSS) tightly integrated navigation system, the general K-means Particle Swarm Optimization (PSO) algorithm was ineffective, and the particle impoverishses and diverges greatly. A novel K-means PSO algorithm was proposed. According to the Geometric Dilution Of Precision (GDOP) of the SINS/GNSS tightly integrated navigation system, the weight of particle was updated, and the weight of each K-means was updated. The novel algorithm was applied in SNS/GNSS tightly integrated navigation system. The simulation result shows that the novel algorithm can restrain the divergence effectively and it improves precision.