In this paper, we propose a novel Iterative Hypergraph Construction and Partition based model fitting method (termed IHCP), for handling multiple-structure data. Specifically, IHCP initially constructs a small-sized hypergraph, and then it performs hypergraph partition. Based on the partitioning results, IHCP iteratively updates the hypergraph by a novel guided sampling algorithm, and performs hypergraph partition. After a few iterations, IHCP is able to construct an effective hypergraph to represent the complex relationship between data points and model hypotheses, and obtain good partitioning results for model fitting as well. IHCP is very efficient since it avoids generating a large number of model hypotheses, and it is also very effective due to the excellent ability of the novel iterative strategy. Experimental results on real images show the superiority of the proposed IHCP method over several state-of-the-art model fitting methods.