In this paper, we deal with geometric model fitting problems on graphs, where each vertex represents a model hypothesis, and each edge represents the similarity between two model hypotheses. Conventional median-shift methods are very efficient and they can automatically estimate the number of clusters. However, they assign the same weighting scores to all vertices of a graph, which can not show the discriminability on different vertices. Therefore, we propose a novel weighted median-shift on graphs method (WMSG) to fit and segment multiple-structure data. Specifically, we assign a weighting score to each vertex according to the distribution of the corresponding inliers. After that, we shift vertices towards the weighted median vertices iteratively to detect modes. The proposed method can adaptively estimate the number of model instances and deal with data contaminated with a large number of outliers. Experimental results on both synthetic data and real images show the advantages of the proposed method over several state-of-the-art model fitting methods.