<p>In this work we explore both the initial nucleation and the stoichiometry of rutile-TiO<sub>2</sub>(001) grown on wurtzite GaN(0001) by radio-frequency O<sub>2</sub>-plasma molecular beam epitaxy. Two studies are performed; in the first, the dependence of the growth on stoichiometry (<em>Ti-rich</em> and <em>O-rich</em>) is observed using reflection high energy electron diffraction and high resolution transmission electron microscopy. In the second study we examine the effect of different initial nucleation surfaces (i.e. <em>Ga-terminated</em> and <em>excess Ga-terminated</em>) and compare the interfaces and bulk crystallinity of the TiO<sub>2</sub>(001) films grown on top of these surfaces. High-resolution transmission electron microscopy and x-ray diffraction measurements show a better interface for TiO<sub>2</sub>(001)/<em>Ga-terminated</em> - GaN(0001) as compared to the TiO2(001)/<em>excess Ga-terminated</em> - GaN(0001).</p>