An attempt was made to develop ultrafine grained Al-Graphite composites through friction stir processing (FSP). Al-Graphite composite was initially prepared using stir casting technique and it subsequently subjected to ultrasonic treatment prior to solidification. The results showed that the ultrasonic treatment during the composite preparation reduced the porosity, graphite particles' agglomeration and the graphite particles' size in the composite. The ultrasonic treated Al-Graphite composite was subjected to a single pass FSP at a constant tool rotational speed of 1600 rpm with three different feed rates, of 20 mm/min, 40 mm/min and 60 mm/min. The microstructure of FSPed composites within the stir zone exhibited a fine recrystallized grain structure due to the combined effect of severe plastic deformation and frictional heat generation during FSP. After the single pass of FSP, the grain size of the composite was reduced from 150 μm to 14 μm, 6 μm and 0.5–1 μm for the tool transverse speeds of 20 mm/min, 40 mm/min and 60 mm/min, respectively. Distribution of graphite particles in Al matrix was significantly improved after FSP process due to the strong stirring action of the rotating tool. Most importantly, microstructural analysis suggested that a substantial reduction in graphite particles' size could be achieved with the aid of FSP process. FSPed Al-Graphite samples exhibited superior hardness as compared to the unprocessed composites due to the uniform dispersion of fine graphite particles in ultra-fine grain structure. In a nutshell, ultrafine grained Al-Graphite composites with uniform dispersion of Graphite nano particles were produced using a single pass FSP process. © 2017 Elsevier B.V.