We propose a new method to enhance the depth images from RGB-D sensors, such as Kinects, by filling the missing/invalid values which are reported by those sensors at certain pixels. We introduce a robust 1D least median of squares (1D LMedS) approach to accurately estimate the depth values of those invalid pixels. We use this approach for efficient traversal of each pixel’s depth values over a se- quence of frames and look for invalid depth values (con- sidered as outliers), and finally, replace those values with stable valid depth values. Our approach solves the unstable nature of depth values in captured scenes that is perceived as flickering. Experimental results show good improvement both for static and moving parts of a scene.