The B12-producing strains Pseudomonas nitroreducens DSM 1650 and Pseudomonas sp. CCUG 2519 (both formerly Pseudomonas denitrificans), with the most distributed pathway among bacteria for exogenous choline/betaine utilization, are promising recombinant hosts for the endogenous production of B12 precursor betaine by direct methylation of bioavailable glycine or non-proteinogenic β-alanine. Two plasmid-based de novo betaine pathways, distinguished by their enzymes, have provided an expression of the genes encoding for N-methyltransferases of the halotolerant cyanobacterium Aphanothece halophytica or plant Limonium latifolium to synthesize the internal glycine betaine or β-alanine betaine, respectively. These betaines equally allowed the recombinant pseudomonads to grow effectively and to synthesize a high level of cobalamin, as well as to increase their protective properties against abiotic stresses to a degree comparable with the supplementation of an exogenous betaine. Both de novo betaine pathways significantly enforced the protection of bacterial cells against lowering temperature to 15 °C and increasing salinity to 400 mM of NaCl. However, the expression of the single plant-derived gene for the β-alanine-specific N-methyltransferase additionally increased the effectiveness of exogenous glycine betaine almost twofold on cobalamin biosynthesis, probably due to the Pseudomonas' ability to use two independent pathways, their own choline/betaine pathway and the plant β-alanine betaine biosynthetic pathway.