The Cross Entropy method is a new search strategy for combinatorial optimization problems. However, it usually needs considerable computational time to achieve good solution quality. This paper introduces a Cross Entropy algorithm for solving maximum clique problem (MCP). To make the Cross Entropy algorithm faster, this paper proposes a leader-based cooperative parallel strategy. Unlike the widely used coarse-grained parallel strategy, our method has a leader, who can move around the parallel processors and collect data actively, and several followers whose main job are simply to sample the cliques guided by the leader via transition matrix. To evaluate the performance of the algorithm, this paper implements the algorithm using OpenMPI on MIMD architecture, and applies it on the MCP benchmark problems. The speedup and efficiency are analyzed, and the results are compared with those obtained by four other best heuristic algorithms. The results show that the presented method has achieved good performance among those best population-based heuristics.