Chemical vapor deposition (CVD) is used as a method for the synthesis of carbon nanotubes (CNT) on substrates, most commonly pre-treated by a metal-catalyst. In this work, the capability of basalt fiber surfaces was investigated in order to stimulate catalyst-free growth of carbon nanotubes. We have carried out CVD experiments on unsized, sized, and NaOH-treated basalt fibers modified by growth temperature and a process gas mixture. Subsequently, we investigated the fiber surfaces by SEM, AFM, XPS and carried out single fiber tensile tests. Growth temperatures of 700 °C as well as 800 °C may induce CNT growth, but depending on the basalt fiber surface, the growth process was differently affected. The XPS results suggest surficial iron is not crucial for the CNT growth. We demonstrate that the formation of a corrosion shell is able to support CNT networks. However, our investigations do not expose distinctively the mechanisms by which unsized basalt fibers sometimes induce vertically aligned CNT carpets, isotropically arranged CNTs or no CNT growth. Considering data from the literature and our AFM results, it is assumed that the nano-roughness of surfaces could be a critical parameter for CNT growth. These findings will motivate the design of future experiments to discover the role of surface roughness as well as surface defects on the formation of hierarchical interphases.