In this paper, we propose a novel graph-based mode-seeking fitting method to fit and segment multiple-structure data. Mode-seeking is a simple and effective data analysis technique for clustering and filtering. However, conventional mode-seeking based fitting methods are very sensitive to the proportion of good/bad hypotheses, while most of sampling techniques may generate a large proportion of bad hypotheses. In this paper, we show that the proposed graph-based mode-seeking method has significant superiority for geometric model fitting. We intrinsically combine mode seeking with preference analysis. This enables mode seeking to be beneficial for reducing the influence of bad hypotheses since bad hypotheses usually have larger residual values than good ones. In addition, the proposed method exploits the global structure of graphs by random walks to alleviate the sensitivity to unbalanced data. Experimental results on both synthetic data and real images demonstrate that the proposed method outperforms several other competing fitting methods especially for complex data.