Graphical models provide a convenient representation for a broad class of probability distributions. \nDue to their powerful and sophisticated modeling capabilities, such models have \nfound numerous applications in machine learning and other areas. In this paper we consider the \ncomplexity of commonly encountered tasks involving graphical models such as the computation \nof the mode of a posterior probability distribution (i.e., MAP estimation), and the computation \nof marginal probabilities or the partition function. It is well-known that such inference problems \nare hard in the worst case, but are tractable for models with bounded treewidth. We ask \nwhether treewidth is the only structural criterion of the underlying graph that enables tractable \ninference. In other words, is there some class of structures with unbounded treewidth in which \ninference is tractable? Subject to a combinatorial hypothesis due to Robertson, Seymour, and \nThomas (1994), we show that low treewidth is indeed the only structural restriction that can \nensure tractability. More precisely we show that for every growing family of graphs indexed \nby tree-width, there exists a choice of potential functions such that the corresponding inference \nproblem is intractable. Thus even for the "best case" graph structures of high treewidth, there is \nno polynomial-time inference algorithm. Our analysis employs various concepts from complexity theory and graph theory, with graph minors playing a prominent role.