CdTe/Te core-shell heterostructures were fabricated by the vapor phase synthesis at low temperatures using a quartz tube furnace. Two step vapor-solid processes were employed. First, various tellurium structures such as nanowires, nanorods, nanoneedles, microtubes and microrods were synthesized under different deposition conditions. These tellurium nanostructures were then used as substrates in the second step to synthesize the CdTe/Te core-shell heterostructures. Using this method, various sizes, shapes and types of CdTe/Te core-shell structures were fabricated under a range of conditions. The temperature, pressure and gas flow rate were very important parameters for synthesizing these nanostructures in the vapor phase process. The morphology, crystal structure and orientation were characterized by field-emission scanning microscopy, field-emission transmission electron microscopy and X-ray diffraction. The vapor phase process at low temperatures appears to be an efficient method for producing a variety of Cd/Te hetero-nanostructures. In addition, the hetero-nanostructures can be tailored to the needs of specific applications by deliberately controlling the synthetic parameters.