A complex system of anastomosing burrows is described from structurally preserved Lower-Middle Pennsylvanian Premnoxylon wood. The burrows are filled with small uniformly shaped coprolites. This discovery represents the oldest recorded evidence for the existence of wood-boring organisms, and indicates that a relatively specialized form of plant-animal interaction was present during the late Paleozoic. It also provides additional support for the idea that Premnoxylon, a cordaitean root, was an aerial organ.