During diamond deposition on titanium substrates, two processes exist: (1) diffusion of hydrogen into a titanium substrate and the formation of hydride thereby degrading the mechanical properties of the substrate; and (2) competition among the rapid diffusion of carbon atoms into substrates, the formation of carbide and the nucleation of diamond crystals (thereby affecting the nucleation and growth rate of the diamond coating). To increase the diamond nucleation rate and prevent the rapid diffusion of hydrogen and carbon into the substrate, different surface treatments and interlayers were studied in this paper. Results showed that polishing with diamond pastes and ultrasonic pre-treatment in diamond suspensions will significantly increase the nuclei density of diamond crystals. However, the diffusion of hydrogen into the substrate could not be prevented. Pre-etching of the titanium substrate using hydrogen plasma for a short time significantly increased the nuclei density of diamond crystals. Results showed that on a TiN interlayer, there was no significant improvement in diamond nucleation and growth, and the deposited diamond coatings showed poor adhesion. New diamond crystals were formed on the DLC interlayer in which DLC acted as the precursor for diamond nucleation. However, the so-formed diamond coating showed spallation. The plasma nitrided layer could prevent the rapid diffusion of hydrogen and carbon into the titanium substrate, but results showed a relatively low nucleation density of diamond crystals and poor adhesion. A graded interlayer combining plasma nitriding followed by plasma carbonitriding was effective in preventing the rapid diffusion of hydrogen and carbon into the substrate and improving the nucleation rate and adhesion of diamond coating.