A co-occurrence of the ichnogenus Phymatoderma and a star-shaped horizontal trace fossil was discovered from Neogene deep-marine deposits (Misaki Formation, central Japan), and is described herein for the first time. Phymatoderma consists of a straight to slightly curved tunnel that shows first- or second-order branches. The tunnels are 5.30–27.25 mm in diameter and are filled with ellipsoidal pellets. The relatively well-preserved star-shaped trace fossil is a large horizontal structure (~18 cm×19 cm) that consists of at least 10 spokes with diameters ranging from 11.49–20.96 mm. As compared to modern analogous surface-feeding traces produced by abyssal echiuran worms and their burrow morphology, it is highly likely that the star-shaped trace fossil and Phymatoderma found from the Misaki Formation are feeding and fecal traces of ancient deep-sea echiurans, respectively. Difference in preservation potential between surface and subsurface traces may result in rare occurrence of star-shaped trace fossils as compared to Phymatoderma. Microscopic observation of the pelletal infill of Phymatoderma also reveals that the trace-maker fed on organic debris and microorganisms such as diatoms and radiolaria.