Nuclear targeting of bacterial proteins is an emerging pathogenic mechanism whereby bacterial proteins can interact with nuclear molecules and alter the physiology of host cells. The fully sequenced bacterial genome can predict proteins that target the nuclei of host cells based on the presence of nuclear localization signal (NLS). In the present study, we predicted bacterial proteins with the NLS sequences from Klebsiella pneumoniae by bioinformatic analysis, and 13 proteins were identified as carrying putative NLS sequences. Among them, HsdM, a subunit of KpnAI that is a type I restriction-modification system found in K. pneumoniae, was selected for the experimental proof of nuclear targeting in host cells. HsdM carried the NLS sequences, 7KKAKAKK13, in the N-terminus. A transient expression of HsdM-EGFP in COS-1 cells exhibited exclusively a nuclear localization of the fusion proteins, whereas the fusion proteins of HsdM with substitutions in residues lysine to alanine in the NLS sequences, 7AAAKAAA13, were localized in the cytoplasm. HsdM was co-localized with importin α in the nuclei of host cells. Recombinant HsdM alone methylated the eukaryotic DNA in vitro assay. Although HsdM tested in this study has not been considered to be a virulence factor, the prediction of NLS motifs from the full sequenced genome of bacteria extends our knowledge of functional genomics to understand subcellular targeting of bacterial proteins.