Today, the use of multi-floor facilities is quite common due to the high land costs and limited areas. However, the locations of the departments on the floor and floor to which departments are assigned become important when considering the total material handling costs, distance traveled and employee movements. The problem where the departments are assigned to which floor and their locations within the floor are determined is called as a multi-floor facility layout problem (MFLP). Different decision variables such as the number of elevators, the location of elevator, the number of floors, and the number of departments increase the complexity of the MFLP. In this study, a two-stage approach is proposed for the solution of MFLP. In the first stage of the proposed approach, the departments are assigned to floors, while in the second stage, the Benders decomposition algorithm is used to determine the locations of departments within the floor in a way to minimize the total material handling costs between the departments. The contribution of the study to the literature is that it is the first study which employs the Benders decomposition algorithm to solve the MFLP. The proposed Benders decomposition algorithm was tested on five problems taken from the literature. In addition, in this paper, three large-scale problems adapted as MFLP were solved. When the results are analyzed, it is seen that the proposed Benders decomposition algorithm was conducted cost improvements ranging 0.12% to 7.64% for five problems taken from the literature.