Titanium is the most used material for implant production. To increase its biocompatibility, continuous research on new coatings has been performed by the scientific community. The aim of the present paper is to prepare new coatings on the surfaces of the pure Ti Grade 2 and the Ti6Al4V alloy. Three types of coatings were achieved by applying anodization and chemical vapor deposition (CVD) methods: TiO nanotubes (TNTs) were formed by anodization, carbon nanotubes (CNTs) were obtained through a metal-catalyst-free CVD process, and a bilayer coating (TiO nanotubes/carbon nanostructures) was prepared via successive anodization and CVD processes. The morphology and structure of the newly developed coatings were characterized using SEM, EDX, AFM, XRD, and Raman spectroscopy. It was found that after anodization, the morphology of the TiO layer on pure Ti consisted of a "sponge-like" structure, nanotubes, and nano-rods, while the TNTs layer on the Ti alloy comprised mainly nanotubes. The bilayer coatings on both materials demonstrated different morphologies: the pure Ti metal was covered by a layer of nanotubular and nano-rod TiO structures, followed by a dense carbon layer decorated with carbon nanoflakes, and on the Ti alloy, first, a TNTs layer was formed, and then carbon nano-rods were deposited using the CVD method.