In the current study, an inexpensive solid-state mechanochemical technique is proposed for the in situ synthesis of nanostructured aluminum nitride (AlN) and carbon nanotubes (CNTs). The CNTs and nitrogen-doped CNTs are synthesized through a novel bottom-up milling approach in which melamine as the solid source of both carbon and nitrogen is milled with aluminum. However, the efficiency of CNT formation remarkably enhances when the milled powder is exposed to a subsequent heat treatment. The effect of various parameters such as milling media, aluminum-to-melamine molar ratio (Al/M), milling time and subsequent heating temperature on the yield and formation mechanism of the produced CNTs are assessed. A detailed characterization of the final products reveals that small amorphous carbon nitride domains resulting from polymerization of melamine molecules at the intermediate stages of milling are responsible for the synthesis of CNTs either during the milling or subsequent heat treatment processes.