Along with methane, methanol and methylated amines represent important biogenic atmospheric constituents, thus not only methanotrophs, but also non-methanotrophic methylotrophs play a significant role in global carbon cycling. The complete genome of a model obligate methanol and methylamine utilizer, Methylobacillus flagellatus (strain KT) was sequenced. The genome is represented by a single circular chromosome of approximately 3 Mb pairs, potentially encoding a total of 2,766 proteins. Based on genome analysis as well as the results from previous genetic and mutational analyses, methylotrophy is enabled by methanol- and methylamine dehydrogenases, the tetrahydromethanopterin-linked formaldehyde oxidation pathway, the assimilatory and dissimilatory branches of the ribulose monophosphate cycle, and by formate dehydrogenases. Some of the methylotrophy genes are present in more than one (identical or non-identical) copy. The obligate dependence on single carbon compounds appears to be due to the incomplete tricarboxylic acid cycle, as no genes potentially encoding alpha ketoglutarate, malate or succinate dehydrogenases are identifiable. The genome of M. flagellatus was compared, in terms of methylotrophy functions, to the previously sequenced genomes of three methylotrophs: Methylobacterium extorquens (Alphaproteobacterium, 7 Mbp), Methylibium petroleophilum (Betaproteobacterium, 4 Mbp), and Methylococcus capsulatus (Gammaproteobacterium, 3.3 Mbp). Strikingly, metabolically and/or phylogenetically, methylotrophy functions in M. flagellatus were more similar to the ones in M. capsulatus and M. extorquens than to the ones in the more closely related M. petroleophilum, providing the first genomic evidence for the polyphyletic origin of methylotrophy in Betaproteobacteria.