All hard, convex shapes are conjectured by Ulam to pack more densely than spheres1, which have a maximum packing fraction of φ = π/√18 ≈ 0.7405. Simple lattice packings of many shapes easily surpass this packing fraction2, 3. For regular tetrahedra, this conjecture was shown to be true only very recently; an ordered arrangement was obtained via geometric construction with φ = 0.7786 (ref. 4), which was subsequently compressed numerically to φ = 0.7820 (ref. 5), while compressing with different initial conditions led to φ = 0.8230 (ref. 6). Here we show that tetrahedra pack even more densely, and in a completely unexpected way. Following a conceptually different approach, using thermodynamic computer simulations that allow the system to evolve naturally towards high-density states, we observe that a fluid of hard tetrahedra undergoes a first-order phase transition to a dodecagonal quasicrystal7, 8, 9, 10, which can be compressed to a packing fraction of φ = 0.8324. By compressing a crystalline approximant of the quasicrystal, the highest packing fraction we obtain is φ = 0.8503. If quasicrystal formation is suppressed, the system remains disordered, jams and compresses to φ = 0.7858. Jamming and crystallization are both preceded by an entropy-driven transition from a simple fluid of independent tetrahedra to a complex fluid characterized by tetrahedra arranged in densely packed local motifs of pentagonal dipyramids that form a percolating network at the transition. The quasicrystal that we report represents the first example of a quasicrystal formed from hard or non-spherical particles. Our results demonstrate that particle shape and entropy can produce highly complex, ordered structures.