We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Without restrictive assumptions on the model, it is unclear whether it is possible to avoid a computationally prohibitive exhaustive search over all possible neighborhoods for each node. In this talk we show how a simple greedy algorithm learns the structure of an Ising model on an arbitrary bounded-degree graph in time quadratic in the number of nodes. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information.