Large mussels of the mytilid subfamily Bathymodiolinae are common inhabitants of deep-sea hydrothermal vents and cold seeps, where gill-borne symbionts allow them to utilize energy-rich compounds such as hydrogen sulfide and methane to support abundant growth. This subfamily also includes smaller symbiont-bearing mussels found on deep-sea wood and organic deposits. Phylogenetic analyses suggest that wood association is ancestral to bathymodiolin evolution. This observation led to the “wooden steps” hypothesis, which proposed that wood and other large organic deposits have acted as evolutionary steppingstones, introducing the progenitors of the modern vent and seep Bathymodiolinae to their remote environments. Although this hypothesis implies an evolutionary trajectory from shallow to deep water, no bathymodiolin species that grows and reproduces at depths less than 100 m has yet been formally described. Here we describe a new bathymodiolin genus and species, Vadumodiolus teredinicola, found growing and reproducing at a depth of 18 m in uninhabited shipworm burrows in the remnants of an ancient submerged bald cypress forest off the coast of Alabama. These results demonstrate that the bathymodiolin radiation has not been limited to deep water and that specific association with wood has led to the successful invasion of both deep and shallow marine environments.