Human detection from depth images is gaining substantial attention since depth information facilitates object extraction from the background. In this paper, we propose a human detection method where search for humans is performed over regions obtained from a pre-segmentation of the depth image. Our segmentation scheme is based on K-means clustering of location, depth values and surface normals of pixels. Once homogeneous regions are determined, the top portion of the boundary of each region in the segmentation map is extracted and matched with realistic head-shoulder template curves. We evaluate our method both on a publicly available dataset, and on our new human detection dataset, which is composed of 500 depth images of humans in diverse poses acquired in varying indoor environments.