Inertial measurement unit (IMU) sensors are widely used for motion analysis in sports and rehabilitation. The attachment of IMU sensors to predefined body segments and sides (left/right) is complex, time-consuming, and error-prone. Methods for solving the IMU-2-segment (I2S) pairing work properly only for a limited range of gait speeds or require a similar sensor configuration. Our goal was to propose an algorithm that works over a wide range of gait speeds with different sensor configurations while being robust to footwear type and generalizable to pathologic gait patterns. Eight IMU sensors were attached to both feet, shanks, thighs, sacrum, and trunk, and 12 healthy subjects (training dataset) and 22 patients (test dataset) with medial compartment knee osteoarthritis walked at different speeds with/without insole. First, the mean stride time was estimated and IMU signals were scaled. Using a decision tree, the body segment was recognized, followed by the side of the lower limb sensor. The accuracy and precision of the whole algorithm were 99.7% and 99.0%, respectively, for gait speeds ranging from 0.5 to 2.2 m/s. In conclusion, the proposed algorithm was robust to gait speed and footwear type and can be widely used for different sensor configurations.