We investigate the phase behavior of tetrapods, hard nonconvex bodies formed by four rods connected under tetrahedral angles. We predict that, depending on the relative lengths of the rods these particles can form a uniaxial nematic phase, and more surprisingly they can exhibit a cubatic phase, a special case of the biaxial nematic phase. These predictions may be experimentally testable, as experimental realizations of tetrapods have recently become available.