The reduction of B-vitamins during food processing necessitates the need for an adequate supply through natural sources. This study aimed to characterise LAB that produce B-vitamins and employ them as starter cultures in milk. LAB were isolated from Nigerian fermented foods and screened for the production of B-vitamins (particularly B2 and B12). Riboflavin overproducers were obtained by selection of natural mutants with roseoflavin. LAB were identified using 16S rRNA gene sequencing and also screened for probiotic and technological characteristics. The best cobalamin and riboflavin producers with probiotic characteristics were used as starters (singly and in a co-culture) to ferment cow milk. The cobalamin and riboflavin content of the milk increased from 2.0 to 7.9 mg/L and from 1.7 to 4.4 mg/L, respectively, using W. cibaria TA94, while L. plantarum KC62 increased the cobalamin and riboflavin levels from 2.0 to 6.9 and 1.7 to 4.4 mg/L, respectively. As combined starter cultures, the cobalamin and riboflavin levels in the cow milk increased from 2.0 to 42.2 mg/L and from 1.7 to 23.8 mg/L, respectively. Lactiplantibacillus plantarum KC62 and Weissella cibaria TA94 are good candidates for designing starter cultures to be used for modulating B-vitamins in specific food applications.