Multi-view video plus depth (MVD) is presented as one of 3D video formats. With color and depth videos, virtual views can be synthesized using depth image based rendering. Due to high complexity of 3D video coding, reduction of the time complexity of depth video coding is essential to success of MVD. Thus, this paper proposes a fast mode decision scheme for depth video coding, aiming at speeding up both mode decision and synthesized-view distortion estimation simultaneously. The proposed scheme includes two stages. First at all, features of color and depth videos are referred to reduce the candidates for mode decision with high prediction accuracy and negligible degradation of rate-distortion (RD) performance. For a depth macroblock (MB) having the co-located MB with high complexity of vertical texture in the reconstructed color video, the second stage further selects the optimal mode using the synthesized-view distortion directed RD cost to reduce the synthesized-view distortion. For fast estimation of synthesized-view distortions, a mathematical approximation of a previous synthesized-view distortion function that mimics view rendering is proposed. Experimental results conducted by JMVC 6.0.3, the reference software of H.264/MVC, show that the proposed scheme achieves significant time reduction with negligible RD performance degradation.