Serial observed gravity anomaly data and a gravity anomaly database map can be used to correct the errors of inertial navigation system based on EKF. Considering a disadvantage in EKF based matching algorithm, low matching accuracy when gravity gradient anomaly along longitude or latitude direction is too small, a fuzzy based parallel filtering matching algorithm is proposed in this paper. Instead of assigning the same weights to fitting points in stochastic linearization process, the fuzzy theory is introduced to assign optimum weights to fitting points. Besides, a bank of parallel Kalman filters are designed to guarantee the robustness of the proposed algorithm. Simulation results in different matching areas show the effectiveness of the proposed algorithm. Compared with the traditional EKF based matching algorithm, the proposed algorithm can provide higher matching accuracy.