We define and study the hexahedron recurrence, a recurrence relation in Z^3 which is similar to the octahedron and cube recurrences. Solutions to the hexahedron recurrence are partition functions for configurations on a certain graph, and have a natural interpretation in terms of cluster algebras. There is an explicit correspondence between monomials in the Laurent expansions arising in the...