A Parallelization of a new Heuristic for the Maximum Clique Problem is described. The heuristic is based on neural networks. The parallelization was performed on a SMP machine using Fortran and Open MP directives. Reasonable speedups were obtained for a variety of test graphs. Further improvements to the heuristic were developed based on the initial parallel results.