Multi-walled carbon nanotubes and other carbon nanostructures have been grown using catalytic thermal chemical vapor deposition method in a horizontal tubular quartz furnace at atmospheric pressure. The mechanisms of nanotubes/nanofibers nucleation and growth are analyzed. A new model explaining the nanotube nucleation as a specific instability occurring on the catalyst particle surface supersaturated with carbon is presented. It is also shown that an axially symmetric instability, giving rise to the nanotube nucleation, is developed when certain critical conditions such as temperature, supersaturation and catalyst volume are achieved. For smaller temperatures, another mechanism of carbon segregation from supersaturated catalyst particles has been observed. In this case, flat rather than tubular graphitic layers are formed. These findings are important for better understanding and control of the synthesis of different carbon nanoforms using chemical vapor deposition.