Layout of construction site facilities has great impact on the project objectives, such as project cost. In this paper, the problem of the construction site facilities layout with many facilities, which is an optimization problem with discrete variables, is considered. Firstly, the problem is transformed to a high-dimensional random sampling problem, and then addressed by a novel meta-heuristic algorithm based on transitional Markov chain Monte Carlo (TMCMC). Different from original TMCMC developed for optimization problems with continuous variables, the proposed meta-heuristic algorithm is based on introducing a sequence of probability distribution functions instead of probability density functions, and thus the method for iteratively generating states of Markov chains is modified in the proposed algorithm, in order to meet the specifics of optimization problems with discrete variables. As shown in an illustrative example, compared with the widely used genetic algorithm, the proposed meta-heuristic algorithm can obtain higher improvement in the stability of achieving global optimal solution.