Due to its wide band gap (3.37 eV) and large exciton binding energy (60 meV), ZnO is of great interest for photonic applications. A number of different morphologies, such as nanobelts, nanowires, tetrapod nanostructures, tubular nanostructures, hierarchical nanostructures, nanobridges, nanonails, oriented nanorod arrays, nanoneedles, nanowalls, and nanosheets, were reported. A range of synthesis methods for fabrication of ZnO nanostructures was reported as well. A common method is evaporation from mixture of ZnO and carbon, which is usually in the form of graphite. In this work, we studied the morphology of the ZnO nanostructures fabricated from the mixture of ZnO (micron-sized and nanoparticles) and carbon (graphite, single-wall carbon nanotubes). When graphite and ZnO powders were used, tetrapod structures were obtained. If one of the reactants was nanosized, the diameter of the tetrapod arms was no longer constant. Finally, when both reactants were nanosized, novel morphologies were obtained. We studied the dependence of the morphology on the amount of starting material and the type of carbon used. The ZnO nanostructures were studied using field emission scanning electron microscopy, transmission electron microscopy, selected area electron diffraction, and X-ray diffraction. Growth mechanism and factors affecting the morphologies are discussed.