Accurate navigation systems are of great importance in intelligent transportation systems and modern connected vehicles technology. Commonly, Global Positioning System (GPS) is integrated with inertial navigation systems (INS) and other sensors to provide robust navigation solution. Currently, the dominant systems integration approach for multi-sensor integrated navigation is Kalman Filter (KF) or Particle Filter (PF). However, KF and PF enhance accuracy only when GPS updates are frequent and accurate enough. During GPS long outages, these integration approaches fail to sustain reliable performance. For these reasons, this work introduces a new systems integration approach that based on a nonlinear systems identification technique called Fast Orthogonal Search (FOS). FOS is a general purpose nonlinear systems modelling method that can model complex nonlinearities. In this work, FOS is proposed to enhance integrated navigation systems performance during long GPS outages. The proposed integration approach is applied on a low-cost 3D land-vehicle multi-sensors navigation system consists of GPS receiver, two horizontal low-cost MEMS-grade accelerometers, single vertical MEMS gyroscope, and the vehicle odometer. The validation of the proposed methodology is verified over real road data and results are be compared to a reference high-end navigation system. Results show improved performance with FOS during GPS outages.