Motivated by the recent synthesis of $beta$-Li$_2$IrO$_3$ -- a spin-orbit entangled $j=1/2$ Mott insulator with a three-dimensional lattice structure of the Ir$^{4+}$ ions -- we consider generalizations of the Kitaev model believed to capture some of the microscopic interactions between the Iridium moments on various trivalent lattice structures in three spatial dimensions. Of particular interest is the so-called hyperoctagon lattice -- the premedial lattice of the hyperkagome lattice, for which the ground state is a gapless quantum spin liquid where the gapless Majorana modes form an extended two-dimensional Majorana Fermi surface. We demonstrate that this Majorana Fermi surface is inherently protected by lattice symmetries and discuss possible instabilities. We thus provide the first example of an analytically tractable microscopic model of interacting SU(2) spin-1/2 degrees of freedom in three spatial dimensions that harbors a spin liquid with a two-dimensional spinon Fermi surface.