The new species of heterocongrine garden eel, Heteroconger guttatus, n. sp., is described from West Papua, Indonesia, based on 42 specimens measuring 188–442 mm TL. It differs from other members of the genus by a distinctive, dense pattern of small, round, orange-brown to dark-brown spots over a pale background on the head and body, becoming smaller ventrally. In addition, the new species is characterized by the dorsal-fin origin anterior to the gill opening; pterygoid teeth present; the body depth at gill opening 28.8–40.2% head length (mean 36.1%); 59–66 preanal vertebrae (mean 63); 164–175 total vertebrae (mean 168.9); and 59–64 preanal lateral-line pores (mean 61). A key is provided for the Indo-West Pacific species of Heteroconger.