We propose a novel stochastic binary local descriptor (STABLE) specifically designed for dense stereo matching in highperformance vision applications. STABLE is a local binary descriptor which builds upon the principles of the compressed sensing theory. The most important properties of STABLE are the independence of the descriptor length from the matching window size and the possibility that more than one pair of pixels contributes to a single descriptor bit. Individual descriptor bits are computed by comparing image intensities over pairs of balanced random sub-sets of pixels chosen from the whole described area. On a synthetic as well as real-world examples we demonstrate that STABLE provides competitive or superior performance than other state-of-the-art local binary descriptors in the task of dense stereo matching. We show that STABLE performs significantly better than the census transform (CT) and local binary patterns (LBP) in all considered geometric and radiometric distortion categories to be expected in practical applications of stereo vision. Moreover, we show as well that STABLE provides comparable or better matching quality than the binary robust independent elementary features (BRIEF) descriptor. The low computational complexity and flexible memory footprint makes STABLE well suited for most hardware architectures.