For very heavy quarks, relations derived from heavy-quark symmetry predict the existence of novel narrow doubly heavy tetraquark states containing two heavy quarks and two light antiquarks. We predict that double-beauty states will be stable against strong decays, whereas the double-charm states and mixed beauty+charm states will dissociate into pairs of heavy-light mesons. Observation of a new double-beauty state through its weak decays would establish the existence of tetraquarks and illuminate the role of heavy color-antitriplet diquarks as hadron constituents.