The Pseudochromis reticulatus complex is diagnosed to include species of Pseudochromis with the combination of a pointed caudal fin (rounded with middle rays produced), a reticulated colour pattern on the upper part of the body, dorsal-fin rays modally III,26, anal-fin rays modally III,15, and pectoral-fin rays modally 18. Members of the complex include P. reticulatus Gill & Woodland, P. pictus Gill & Randall, P. tonozukai Gill & Allen, P. jace Allen, Gill & Erdmann and P. stellatus new species. The last-named is herein described from six specimens from Batanta and Batu Hitam in the Raja Ampat Islands, West Papua, Indonesia. It is distinguished from other members of the complex in live coloration, and in having higher mean numbers of scales in lateral series and of anterior lateral-line scales (36–38 and 29–32, respectively), and a deeper body as measured from the dorsal-fin origin to pelvic-fin origin (31.8–33.5 % SL).