Hyphomicrobium nitrativorans strain NL23 has been isolated from the biofilm of a denitrification system treating seawater. This strain has the capacity to denitrify using methanol as a carbon source. Here, we report the complete genome sequence of this strain in an effort to increase understanding of the function of this bacterium within the biofilm.