Range Imaging (RI) has sparked an enthusiastic interest recently due to the numerous applications that can benefit from the presence 3D data. One of the most successful techniques for RI employs Time-of-Flight (ToF) cameras which emit and subsequently record laser pulses in order to estimate the distance between the camera and an object. A limitation of this class of RI is the requirement for a large number of frames that have to be captured in order to generate high resolution depth maps. In this work, we propose a novel approach for ToF based RI that utilizes the recently proposed framework of Compressed Sensing to dramatically reduce the number of necessary frames. Our technique employs a random gating function along with state-of-the-art minimization techniques in order to estimate the location of a returning laser pulse and infer the distance. To validate the theoretical motivation, software simulations were carried out. Our simulated results have shown that reconstruction of a depth map is possible from as low as 10% of the frames that traditional ToF cameras require with minimum reconstruction error while 20% sampling rates can achieve almost perfect reconstruction in low resolution regimes. Our experimental results have also shown that the proposed method is robust to various types of noise and applicable to realistic signal models. © (2012) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.