An algorithm for pedestrian navigation with foot-mounted inertial measurement units (IMUs) based on the extended Kalman filter is presented. Its novelty is in adaptation of state covariances according to some diagnostic tests performed on the pedestrian’s trajectory. Two IMUs attached to both feet are needed for the algorithm work. Navigation solution is aided with information about bounded distance between feet and information about pedestrian’s straight-line motion. The latter is used for diagnostic tests needed for covariances adaptation. The algorithm was tested on real data and showed better performance and reliability than known heuristic drift elimination algorithms, which use information about straight-line motion to compensate heading drift