A tightly integrated magnetic-field aided inertial navigation system is presented. The system uses a magnetometer sensor array to measure spatial variations in the local magnetic-field. The variations in the field are - via a recursively updated polynomial magnetic-field model - mapped into displacement and orientation changes of the array, which in turn are used to aid the inertial navigation system. Simulation results show that the resulting navigation system has three orders of magnitude lower position error at the end of a 40 seconds trajectory as compared to a standalone inertial navigation system. Thus, the proposed navigation solution has the potential to solve one of the key challenges faced with current magnetic-field simultaneous localization and mapping (SLAM) systems - the very limited allowable length of the exploration phase during which unvisited areas are mapped.