While multi-layer perceptrons (MLPs) remain popular for various classification tasks, their application of gradient-based schemes for training leads to some drawbacks including getting trapped in local optima. To tackle this, population-based metaheuristic methods have been successfully employed. Among these, Lévy flight distribution (LFD), which explores the search space through random walks based on a Lévy distribution, has shown good potential to solve complex optimisation problems. LFD uses two main components, the step length of the walk and the movement direction, for random walk generation to explore the search space. In this paper, we propose a novel MLP training algorithm based on the Lévy flight distribution algorithm for neural network-based pattern classification. We encode the network’s parameters (i.e., its weights and bias terms) into a candidate solution for LFD, and employ the classification error as fitness function. The network parameters are then optimised, using LFD, to yield an MLP that is trained to perform well on the classification task at hand. In an extensive set of experiments, we compare our proposed algorithm with a number of other approaches, including both classical algorithms and other metaheuristic approaches, on a number of benchmark classification problems. The obtained results clearly demonstrate the superiority of our LFD training algorithm.