Advancements in the synthesis of faceted nanoparticles and colloids have spurred interest in the phase behavior of polyhedral shapes. Regular tetrahedra have attracted particular attention because they prefer local symmetries that are incompatible with periodicity. Two dense phases of regular tetrahedra have been reported recently. The densest known tetrahedron packing is achieved in a crystal of triangular bipyramids (dimers) with a packing density of 4000/4671 ≈ 85.63%. In simulation a dodecagonal quasicrystal is observed; its approximant, with periodic tiling (3.4.3(2).4), can be compressed to a packing fraction of 85.03%. Here, we show that the quasicrystal approximant is more stable than the dimer crystal for packing densities below 84% using Monte Carlo computer simulations and free energy calculations. To carry out the free energy calculations, we use a variation of the Frenkel-Ladd method for anisotropic shapes and thermodynamic integration. The enhanced stability of the approximant can be attributed to a network substructure, which maximizes the free volume (and hence the wiggle room) available to the particles and facilitates correlated motion of particles, which further contributes to entropy and leads to diffusion for packing densities below 65%. The existence of a solid-solid transition between structurally distinct phases not related by symmetry breaking--the approximant and the dimer crystal--is unusual for hard particle systems.