Among natural fibers, basalt fibers have recently emerged as the main candidate to replace glass fibers in composite materials. Since the fiber/matrix interface strongly influences the final mechanical properties in a fiber reinforced composite, the current aim is to optimize the efficiency of the load transfer between the two different phases in the composite by growing carbon nanostructures (CNS), both nanofibers and nanotubes, on the surface of unsized basalt fibers exploiting less common catalysts compared to transition metals. Carbon nanostructures were grown onto unsized basalt fibers by chemical vapor deposition under different growth temperatures, using three different catalysts: copper, sodium, and iron. Considering the negative influence that high temperature has on the mechanical properties of basalt fibers, by lowering the synthesis temperature, we preserved the intrinsic properties of the basalt fibers, losing only 5% of the tensile strength at 300 °C growth temperature with a copper-based catalyst, while obtaining dense and uniform CNS growth. The different morphologies of the CNS obtained on the surface of the fibers were investigated by morphological and spectroscopic analyzes, while fiber/matrix adhesion was characterized by single fiber pull out tests, showing increases of 30% and 60% in interfacial shear strength and total pull out work, respectively. These less common catalysts provide an expanded design strategy for obtaining composites with improved interfacial bonding and multifunctional properties.