The Allmusic review by Brian Bartolini awarded the album 4½ stars stating "Tremendous taste prevents Holland from making unsatisfying music. He is a great leader in the truest senses of the word -- he gives his team space, trusts their abilities and judgment, yet all the while remains firmly in command and infuses the results with his own style and personality. Prime Directive is a wonderful jazz album. These 77 minutes and nine tracks do not cheat or disappoint... Prime Directive is recommended; a great leader is, indeed, hard to find". In 2000 the well-respected Jazz Journalists Association honored the album with their award Record of the Year.