This paper considers the two-stage capacitated facility location problem (TSCFLP) in which products manufactured in plants are delivered to customers via storage depots. Customer demands are satisfied subject to limited plant production and limited depot storage capacity. The objective is to determine the locations of plants and depots in order to minimize the total cost including the fixed cost and transportation cost. However, the problem is known to be NP-hard. A practicable exact algorithm is impossible to be developed. In order to solve large-sized problems encountered in the practical decision process, an efficient alternative approximate method becomes more valuable. This paper aims to propose a hybrid evolutionary algorithm framework with machine learning fitness approximation for delivering better solutions in a reasonable amount of computational time. In our study, genetic operators are adopted to perform the search process and a local search strategy is used to refine the best solution found in the population. To avoid the expensive consumption of computational time during the fitness evaluating process, the framework uses extreme machine learning to approximate the fitness of most individuals. Moreover, two heuristics based on the characteristics of the problem is incorporated to generate a good initial population. Computational experiments are performed on two sets of test instances from the recent literature. The performance of the proposed algorithm is evaluated and analyzed. Compared with other algorithms in the literature, the proposed algorithm can find the optimal or near-optimal solutions in a reasonable amount of computational time. By employing the proposed algorithm, facilities can be positioned more efficiently, which means the fixed cost and the transportation cost can be decreased significantly, and organizations can enhance competitiveness by using the optimized facility location scheme. (C) 2016 Elsevier Ltd. All rights reserved.