High yield synthesis of bamboo-like multi-walled carbon nanotubes (BCNTs) over a novel zeolite catalyst has been achieved using acetonitrile as a carbon source. The synergism of nickel (Ni) and rare earth oxides (REO) in the zeolites is considered very important for the high activity of the catalysts for the rapid decomposition of acetonitrile and diffusion of carbon. The yield of BCNTs increases with the Ni content and the growth time. The as-grown BCNTs are arranged in the form of flower-like clusters surrounding each zeolite. This CNT-zeolite composite may be regarded as a complex zeolite which will be very useful for the selective absorption, filtration and storage of gas.