Multi-core central processing units (CPU) and the graphics processing unit (GPU) have become popular parallel computing platforms in recent years [1]. The GPU platform is commonly adopted in the research community as it has been to be superior to the traditional CPU. Straightforward implementations of Parallel algorithms on a GPU can easily achieve a speedup of ten times or more over the sequential algorithms. However, achieving significant speedup on a multi-core CPU (over the sequential algorithm) requires intelligently designed and well-optimized algorithms [3]. This paper discusses a parallel implementation of A* search which achieved 6.67x Speedup with a search space of 106 nodes, 3.14x speedup with 107 nodes, and 137.67x speedup with 108 nodes when run on the eight-core, 3.0 GHz Intel Core i7 processor. This paper also analyses different work partitioning strategies and how the performance of the parallel A* search algorithm scales.