Recently, there has been much effort in understanding topological phases of matter with gapless bulk excitations, which are characterized by topological invariants and protected intrinsic boundary states. Here we show that topological semimetals of Majorana fermions arise in exactly solvable Kitaev spin models on a series of three-dimensional lattices. The ground states of these models are quantum spin liquids with gapless nodal spectra of bulk Majorana fermion excitations. It is shown that these phases are topologically stable as long as certain discrete symmetries are protected. The corresponding topological indices and the gapless boundary states are explicitly computed to support these results. In contrast to previous studies of noninteracting systems, the phases discussed in this work are novel examples of gapless topological phases in interacting spin systems.