We study the following structure learning problem forH-colorings. For a fixed (and known) constraint graphHwithqcolors, given access to uniformly randomH-colorings of an unknown graphG=(V,E), how many samples are required to learn the edges of G? We give a characterization of the constraint graphs Hfor which the problem is identifiable for every Gand show that there are identifiable constraint graphs for which one cannot hope to learn every graph Gefficiently. We provide refined results for the case of proper vertexq-colorings of graphs of maximum degree d. In particular, we prove that in the tree uniqueness region (i.e., whenq≤ d), the problem is identifiable and we can learnGin poly(d,q)× O(n2logn) time. In the tree non-uniqueness region (i.e., when q≤ d), we show that the problem is not identifiable and thusGcannot be learned. Moreover, whenq ≤ d- √d + Θ (1), we establish that even learning an equivalent graph (any graph with the same set ofH-colorings) is computationally hard—sample complexity is exponential innin the worst case. We further explore the connection between the efficiency/hardness of the structure learning problem and the uniqueness/non-uniqueness phase transition for generalH-colorings and prove that under a well-known uniqueness condition in statistical physics, we can learnGin poly(d,q)× O(n2logn) time.