A textured coating of zirconia on Ti-6Al-4V alloy was produced using pulsed laser based processing technique. Scanning electron microscope observations coupled with fractal analysis revealed the multi-scale nature of the textured coating. Both stylus based profilometric measurements and fractal analysis indicated non-linear nature of the relationship between laser processing speed at constant pulse frequency (10 kHz) and roughness of the textured coating. The textured coatings produced with all the three processing speeds (40, 160, 290 cm/min) were fractal over certain length scales. Processing at 40 cm/min resulted in structures that are fractal across a large number of length scales where as higher processing speeds resulted in fractality over fewer length scales. The processing speed influenced the zirconia content in the coating and the phase transformation within Ti-matrix of the coating. Within the coating, while zirconia content decreased the amount of retained beta-Ti increased with increase in processing speed. Such physical and chemical transformations are desired in a titanium bio-implant for effective contact with protein, cells and tissues at various length scales and its effective chemical performance in bio-environment.