Identifying hadronic molecular states and/or hadrons with multi-quark components either with or without exotic quantum numbers is a long standing challenge in hadronic physics. We suggest that studying the production of these hadrons in relativistic heavy ion collisions offer a promising resolution to this problem as yields of exotic hadrons are expected to be strongly affected by their structures. Using the coalescence model for hadron production, we find that compared to the case of a non-exotic hadron with normal quark numbers, the yield of an exotic hadron is typically an order of magnitude smaller when it is a compact multi-quark state and a factor of two or more larger when it is a loosely bound hadronic molecule. We further find that due to the appreciable numbers of charm and bottom quarks produced in heavy ion collisions at RHIC and even larger numbers expected at LHC, some of the newly proposed heavy exotic states could be produced and realistically measured in these experiments.