Abstract: We investigate the production of exotic tetraquarks, QQ (q) over bar (q) over bar T-QQ (Q = c or b and q = u or d), in relativistic heavy-ion collisions using the quark coalescence model. The T-QQ yield is given by the overlap of the density matrix of the constituents in the emission source with the Wigner function of the produced tetraquark. The tetraquark wave function is obtained from exact solutions of the four-body problem using realistic constituent models. The production yields are typically one order of magnitude smaller than previous estimations based on simplified wave functions for the tetraquarks. We also evaluate the consequences of the partial restoration of chiral symmetry at the hadronization temperature on the coalescence probability. Such effects, in addition to increasing the stability of the tetraquarks, lead to an enhancement of the production yields, pointing towards an excellent discovery potential in forthcoming experiments. We discuss further consequences of our findings for the search of exotic tetraquarks in central Pb + Pb collisions at the LHC.