Aiming at the problems of early maturity and insufficient convergence of fruit fly optimization algorithm (FOA), a novel FOA with chaotic step  is proposed by using Hénon chaotic mapping as the step factor. The proposed algorithm uses the good ergodicity and diversity of the chaotic phenomena generated by Hénon mapping to improve the fixed step of FOA, and increase the magnification coefficient to improve the global and local search ability and the capability of jumping out the local optimal solutions. The proposed algorithm is verified by 10 classical test functions, and compared with several algorithms. The results show that the proposed algorithm has a high ability of global search and jumping out of local optimal solutions.