Numerous applications of Eikonal equations prompted the development of many efficient numerical algorithms. The Heap-Cell Method (HCM) is a recent serial two-scale technique that has been shown to have advantages over other serial state-of-the-art solvers for a wide range of problems [A. Chacon and A. Vladimirsky, SIAM J. Sci. Comput., 34 (2012), pp. A547--A578]. This paper presents a parallelization of HCM for a shared memory architecture. The numerical experiments in show that the parallel HCM exhibits good algorithmic behavior and scales well, resulting in a very fast and practical solver.