Abstract: In view of problem that traditional inertial navigation technology of mobile phone is unable to calculate steps or step length accurately, a trajectory generation algorithm of inertial navigation based on smart phone was put forward. The walking steps of people are calculated by use of step counting algorithm based on Mealy state machine according to three-axis accelerations of walking people captured by three-axis acceleration sensor of smart phone, and start-stop timestamp of each step is gotten. Direction change of each step is calculated according to data of three-axis gyroscope and the start-stop timestamp of each step combined with compass reading. Step length is estimated based on the least square method considering different acceleration of walking people with different step length. Coordinate relative to starting point of each step is calculated on the basis of coordinate of the starting point, step length and direction change, so as to get movement trajectory of people. The simulation result shows that the algorithm can achieve high accuracy of inertial navigation.