This study concerns the efficacy of partial agar substitution by galactomannans as support in plant regeneration media for Nicotiana tabacum. The production of multiple shoots from leaf-derived callus and their rooting were evaluated. The galactomannans applied were obtained from Cassia fastuosa (cassia) and Cyamopsis tetragonolobus (guar gum – a commercial galactomannan) seeds. The results obtained on media solidified with mixtures of agar/galactomannan (3 g dm−3 each) gels were compared with those on media gelled with a standard concentration of agar (6 g dm−3). The in vitro performance allowed to conclude that the use of galactomannans raised the number of shoots and improved their quality. Furthermore, the length of roots and the size of leaves were significantly higher in the media solidified with agar/guar galactomannan mixtures.