This paper introduces a new algorithm named Elitist Stepped Distribution Algorithm (ESDA), which is inspired from the existing Cross Entropy Method (CEM) through the modification of elite sample based normal distribution used in CEM. Considering the natural behavior of normal distribution, ESDA is proposed to enhance the drawbacks of CEM through improving the efficiency in both exploration and exploitation processes when applying for complex function optimization problems. In ESDA, the elite sample percent defined in CEM is separated into two parts: (1) elite sample percent to calculate the mean value, and (2) elite sample percent to calculate standard deviation of normal distribution to construct an applicable balance between exploration and exploitation ability of the algorithm at a reasonable convergence speed. The elite sample percent parameter for the mean guides the algorithm to focus more on the better solutions and therefore improves the exploitation ability, whereas the elite sample percent parameter for the standard deviation controls the length of standard deviation to handle the exploration process more effectively. Performance of ESDA is investigated using unconstrained benchmark problems and compared with CEM, Simple Genetic Algorithm and Particle Swarm Optimization. The comparisons on unimodal and multi-modal functions confirm the efficiency of the algorithm in both exploration and exploitation process. In addition, the performance of ESDA is tested using constrained engineering problems commonly used in literature by comparing its performance with the other ones statistically. The results on engineering problems also prove that ESDA is perfectly applicable in real-world applications. (C) 2017 Elsevier B.V. All rights reserved.