Abstract: Omni-directional walking parameters of a humanoid robot have great impacts on its walking stability, flexibility and rapidity. However, it is difficult to establish the mathematical relationship between the physical robot and the simplified dynamics model which describes its inter-pace connectivity constraints. Therefore, it is hard to obtain the expression of the optimization objective as well as the optimization method. In this paper, seven key effective parameters are extracted from the stride tracking planning algorithm, and the tracking quality of a standard walking experiment is designated as the optimization objective. The problem is thus transferred into a black-box optimization process. Kriging surrogate model is established by dynamics simulation, and the initial experiments designed with Latin Hypercube as well as the EGO (effective global optimization) iterative modeling and optimization are adopted to solve this problem. Dynamics simulation results show that the omni-directional walking parameters are optimized via the proposed approach with quite a little experiment cost. The approach is also able to promote remarkably the walking speed and stride tracking ability simultaneously.