Depth map stereo correspondence techniques are described. In one or more implementations, a depth map generated through use of a depth sensor is leveraged as part of processing of stereo images to assist in identifying which parts of stereo images correspond to each other. For example, the depth map may be utilized to describe depth of an image scene which may be used as part of a stereo correspondence calculation. The depth map may also be utilized as part of a determination of a search range to be employed as part of the stereo correspondence calculation.