Magnesium matrix composite reinforced by titanium alloy (Ti-6Al-4V) particulate was fabricated by powder metallurgy route. The samples of composite were hot-extruded with an ultra-deformation ratio of 225:1. The microstructures of extruded samples were investigated using optical microscopy, scanning electron microscopy (SEM) and transmission electron microscopy (TEM). The results showed that the Ti-6Al-4V particulates were apparently elongated along the extrusion direction, thus increased its reinforcing effect on the matrix. The ultra-deformation could markedly decrease the grain sizes of the composite matrix, and greatly improve the homogeneity of microstructures when compared with a lower ratio of extrusion deformation; in addition, the oxide layers on the surface of original Mg particles were effectively broken and dispersed randomly in the vicinity of Mg-Mg interfaces. It produced an oxidedispersion-strengthening (ODS) effect, further reinforced the matrix as a kind of secondary reinforcement.