Object localization techniques have significant applications in civil fields and safety problems. A novel analytical formula is developed for accurate underwater and aerial object real-time localization by combining gravitational field and horizontal gravitational gradient anomalies. The proposed method enhances the accuracy of object localization and its excess mass estimation; it also effectively avoids the possible numerical instability and the singularity in the previous works. Finally, a synthetic underwater object navigation model was adopted to verify its performance. The results show that our newly developed method is more practical than existing methods.