Azotobacter vinelandii produces the biopolymer alginate, which has a wide range of industrial and pharmaceutical applications. A random transposon insertion mutant library was constructed from A. vinelandii ATCC12518Tc in order to identify genes and pathways affecting alginate biosynthesis, and about 4,000 mutant strains were screened for altered alginate production. One mutant, containing a mucA disruption, displayed an elevated alginate production level, and several mutants with decreased or abolished alginate production were identified. The regulatory proteins AlgW and AmrZ seem to be required for alginate production in A. vinelandii, similarly to Pseudomonas aeruginosa. An algB mutation did however not affect alginate yield in A. vinelandii although its P. aeruginosa homolog is needed for full alginate production. Inactivation of the fructose phosphoenolpyruvate phosphotransferase system protein FruA resulted in a mutant that did not produce alginate when cultivated in media containing various carbon sources, indicating that this system could have a role in regulation of alginate biosynthesis. Furthermore, impaired or abolished alginate production was observed for strains with disruptions of genes involved in peptidoglycan biosynthesis/recycling and biosynthesis of purines, isoprenoids, TCA cycle intermediates, and various vitamins, suggesting that sufficient access to some of these compounds is important for alginate production. This hypothesis was verified by showing that addition of thiamine, succinate or a mixture of lysine, methionine and diaminopimelate increases alginate yield in the non-mutagenized strain. These results might be used in development of optimized alginate production media or in genetic engineering of A. vinelandii strains for alginate bioproduction.