<p>This article presents velocity-aided leg inertial nonlinear odometry and registration (VALINOR), a method for lightweight yet accurate leg-inertial odometry for humanoid robots. VALINOR builds upon the tilt observer, a complementary filter that estimates the IMU’s tilt and linear velocity with strong mathematical convergence guarantees, associating it with leg odometry. We introduce an axis-agnostic fusion method that coherently combines the tilt observer’s tilt estimate with the leg odometry’s yaw. We argue that this method is less arbitrary and more mathematically sound than those based on other orientation representations, especially on Euler angles. We validate VALINOR on real-world experiments with two humanoid robots. Results show that, while being 7.5 times faster than the state-of-the-art method used for comparison, VALINOR achieves estimation performance on par with it. This makes VALINOR a strong candidate for feedback in balance control, as well as for task planning and execution within the robot’s local workspace. Beyond this contribution, we hope to highlight the broader need for estimation methods that are not only accurate and efficient, but also grounded in strong mathematical guarantees, towards their safe deployment around humans.</p>