Al2O3-TiO2 composite is known as a material which has high hardness and high corrosion resistance but low fracture toughness. The addition of graphite is suitable used as reinforcement in improving the low fracture toughness of Al2O3-TiO2 matrix composite since graphite act as a solid lubricant which can improve the wear resistance and has extremely good lubrication performance. In coating application, the fine powder size of Al2O3-TiO2-graphite composites is required. The conventional powder metallurgy technique of Al2O3-TiO2-graphite composites require a long period of time to achieve finest particle size owing to low energy milling. Hence, using high energy planetary mill, the finest particle size can be achieved in a short time. In this study, the effects of milling time (2, 4, 8 and 10 h) and milling speed (200, 250 and 300 rpm) on the structural and microstructural of Al2O3-TiO2-graphite nanocomposite were investigated. The phase analysis and microstructure of nanocomposite were characterized using X-Ray Diffraction (XRD) and Scanning Electron Microscope (SEM) equipped with an Energy Dispersive X-Ray (EDX) elemental analysis. Increasing milling time up to 10 h at 300 rpm contributes to a small solubility between Al2O3 and TiO2. The crystallite size of Al2O3 decreased and the internal strain increased with increasing milling time and milling speed. The morphology of milled powders showed the composite particles size and shape decreased with increasing milling time. Increasing milling time and speed produce finer and flaky shape of Al2O3-TiO2-graphite particles which then affects the green density of the composite.