Systems and methods for using magnetic field readings to refine device location estimates are provided. As an example, a plurality of magnetic field readings can be collected by a device as it travels along a path. A positioning system (e.g., GPS) or other sensors can be used to provide a coarse location for the device at each reading. A contribution to each of the magnetic field readings by the Earth's magnetic field can be removed to obtain a plurality of residual readings and a plurality of regions of interest along the path can be identified based at least in part on the residual readings. The regions of interest can be compared to each other to identify a plurality of correspondences between magnetic field readings or residual readings and the plurality of correspondences can be used to refine the location estimates.