This paper reports on a new back propagation (BP) neural network based on an improved shuffled frog leaping algorithm (ISFLA) and its application in bearing fault diagnosis. The ISFLA is developed on the basis of a chaotic operator and the convergence factor of particle swarm optimization to overcome the shortcomings of conventional shuffled frog leaping algorithm (SFLA). Testing results show that the proposed algorithm can effectively improve the solution accuracy and convergence properties and exhibits an excellent ability of global optimization in high-dimensional space. The presented ISFLA is then employed to optimize the weights and threshold values of BP neural network. An ISFLA-BP network model is established for the early fault diagnosis of rolling bearings. The proposed ISFLA-BP scheme has been compared with BP and SFLA-BP networks through experimental studies. Results indicate that the developed new model demonstrates better generalization capability and stronger robustness. It is able to effectively improve the efficiency of network training and the accuracy of early fault pattern recognition in bearing fault diagnosis tasks.