Heuristic search is a fundamental component of artificial intelligence applications. Because search routines are frequently a computational bottleneck, numerous methods have been explored to increase the efficiency of search. While sequential search methods use exponential amounts of storage and yield exponential run times, parallel algorithms designed for MIMD machines significantly reduce the time spent in search. In this paper, we present a massively- parallel SIMD approach to search named MIDA* search. The components of MIDA* include a very fast distribution algorithm which biases the search to one side of the tree, and an incrementally-deepening depth-first search of all the processors in parallel. We show the results of applying MIDA* to instances of the fifteen puzzle problem. Results reveal an efficiency of 76% and a speedup of 8553% and 492% over serial and 16- processor MIMD algorithms, respectively.