Lin0431 protein from Listeria innocua (UniProtKB/TrEMBL ID Q92EM7/Q92EM7_LISIN) was selected as a target of the Northeast Structural Genomics Consortium (target ID: LkR112). Here, we present the high-quality NMR solution structure of this protein which is the first representative for a member of DUF1312 domain family. Lin0431 protein exhibits a β-sandwich topology. Four anti-parallel β-strands form one face of the sandwich and the other three anti-parallel β-strands together with a short α-helix form the other face of the sandwich. Structure alignment by Dali reveals an unexpected structural similarity with domain II of NusG from Aquifex aeolicus. Analyses of the electrostatic protein surface potential and searches for protein surface cavities reveal the conserved basic charged surface cavities of both the Lin0431 and domain II of AaeNusG, suggesting they may bind the negatively charged nucleic acids and/or and other binding partners. The high structural similarity and similar surface features, despite the lack of recognizable sequence similarity, between Lin0431 and AaeNusG domain II suggest that the domain II of NusG and DUF1312 domains have a homologous relationship and may share similar biochemical functions.