For every class of relational structures , let HOM be the problem of deciding whether a structure has a homomorphism to a given arbitrary structure . Grohe has proved that, under a certain complexity-theoretic assumption, HOM is solvable in polynomial time if and only if the cores of all structures in have bounded tree-width. We prove (under a weaker complexity-theoretic assumption) that the corresponding counting problem #HOM is solvable in polynomial time if and only if all structures in have bounded tree-width. This answers an open question posed by Grohe.