The trace fossil Phymatoderma cf. granulata is described for the first time from the deep-marine deposits of the Hayama Group (Miocene) of Japan. This ichnotaxon is a burrow system composed of horizontal, straight to slightly curved tunnels ranging from 7.7 to 20.4mm in diameter (mean=14.98 mm), occasionally representing branching. Each tunnel is filled with ellipsoidal pellets with aspect ratios generally ranging from 1.4 to 2.4. Based on the comparison between the Hayama specimens and other Phymatoderma specimens from tectonically and paleoenvironmentally similar settings, a deep-sea echiuran worm is suggested as the possible trace-maker. Morphometric analysis demonstrates that the pellet aspect ratios do not show any correlation with the tunnel diameter, suggesting that there was not a significant change in digestive and/or excretory systems from the smaller to the larger trace-producing animals. In addition, microscopic analysis of the pelletal infill of P. cf. granulata revealed that the trace-maker actually fed on freshly deposited organic detritus and microorganisms, such as planktic foraminifera and radiolaria.