Predicting the next foot placement of humans during walking can help improve compliant interactions between humans and walking aid robots. Previous studies have focused on foot placement estimation with wearable inertial sensors after heel-strike, but few have predicted foot placements in advance during the early swing phase. In this study, a Bayesian inference-based foot placement prediction approach was proposed. Possible foot placements were modeled as a probability distribution grid map. With selected foot motion feature events detected sequentially in the early swing phase, the foot placement probability map could be updated iteratively using the feature models we built. The weighted center of the probability distribution was regarded as the predicted foot placement. Prediction errors were evaluated with collected walking data sets. When testing with the data from inertial measurement units, the prediction errors were (5.46 cm ± 10.89 cm, -0.83 cm ± 10.56 cm) for cross-velocity walking data and (-4.99 cm ± 12.31 cm, -11.27 cm ± 7.74 cm) for cross-subject-cross-velocity walking data. The results were comparable to previous works yet the prediction could be made earlier. For the subject who walked with more stable gaits, the prediction error can be further decreased. The proposed foot placement prediction approach can be utilized to help walking aid robots adjust their pose before each heel-strike event during walking, which will make human-robot interactions more compliant. This study is also expected to inspire additional probabilistic gait analysis works.