Training deep classifiers for Extreme Multi-Label Classification (XMC) is difficult due to the computational and memory costs that arise from extremely large label sets. Traditionally, the final output layer of these deep classifiers scale linearly with the size of the label set (e.g., the number of products that can be recommended on an E-commerce website). In many realistic settings, deep classifiers need to be able to accurately classify over one million different labels. Consequently, deep classifiers for realistic tasks can quickly explode in size and become difficult to train and store. Reducing the size of deep classifiers for XMC is imperative to (i) train them more efficiently and (ii) deploy them in memory-constrained settings of interest, such as mobile devices. We address the current limitations of deep classifiers by proposing a novel XMC method, DECLARE: Deep Extreme Compressed Labeling And Recovery Estimation. DECLARE compresses the labels into a much smaller dimension, distilling down key information from the original space, allowing more efficient deep classifier training and storage. Finally, DECLARE recovers the most-likely predicted labels in the original label space. Empirically, we find that DECLARE is able to compress labels by nearly four magnitudes while simultaneously outperforming uncompressed performance.