This paper presents a segmentation-based stereo matching algorithm using an adaptive multi-cost approach, which is exploited for obtaining accuracy disparity maps. The main contribution is to integrate the appealing properties of multi-cost approach into the segmentation-based framework. Firstly, the reference image is segmented by using the mean-shift algorithm. Secondly, the initial disparity of each segment is estimated by an adaptive multi-cost method, which consists of a novel multi-cost function and an adaptive support window cost aggregation strategy. The multi-cost function increases the robustness of the initial raw matching costs calculation and the adaptive window reduces the matching ambiguity effectively. Thirdly, an iterative outlier suppression and disparity plane parameters fitting algorithm is designed to estimate the disparity plane parameters. Lastly, an energy function is formulated in segment domain, and the optimal plane label is approximated by belief propagation. The experimental results with the Middlebury stereo datasets, along with synthesized and real-world stereo images, demonstrate the effectiveness of the proposed approach.