In this paper we present a genetic algorithm (GA) for solving NP-hard Multiple Warehouse Layout Problem (MLWLP). New encoding scheme with appropriate objective functions is implemented. Specific representation and modified genetic operators keep individuals correct and help in restoring good genetic material and avoiding premature convergence in suboptimal solutions. The algorithm is tested on instances generated to simulate real life problems. Experimental results show that the algorithm reaches most of optimal solutions for problems containing up to 40 item types. The algorithm is successfully tested on large scale problem instances that can not be handled by CPLEX solver due to memory limits.