In this paper, we introduce a novel hash learning framework for multi-label learning which employs structured prediction. A hash function is learned to embed samples in Hamming spaces, and for each label, a pair of codewords are simultaneously inferred from the available data. These codewords are then used to determine label predictions based on Hamming proximity. The key advantage of this framework is its computational efficiency in tackling multi-label problems without making restrictive, simplifying assumptions about the structure of the output space, or developing problem-dependent heuristics. Our method not only enjoys considerably better scalability while capturing label inter-dependence, but also yields an exact training algorithm. Experimental results on a collection of benchmark multi-label datasets demonstrate that our model attains higher performance over alternative state-of-the-art multi-label approaches. It is also worth noting that our method can be extended to semi-supervised and missing labels scenarios.