We present a scheme for effciently constructing high-dimensional cluster state using probabilistic entangling quantum gates. It is shown that the required computational overhead scales effciently both with 1/P and n even if all the entangling quantum gates only succeed with an arbitrary small probability, where p is the success probability of the entangling quantum gate and n is the number of qubits in the computation.