In the present work we studied microstructure of ultra fine grained (UFG) pure Mg and UFG Mg-based alloys. The initial coarse grained samples were deformed by high pressure torsion (HPT) using pressure of 6 GPa. Such deformation leads to formation of UFG structure in the samples. The severe plastic deformation results in creation of high number of lattice defects. Therefore, we used positron annihilation spectroscopy (PAS) for defect characterizations. PAS represents a well developed non-destructive technique with high sensitivity to open volume defects like vacancies, vacancy clusters, dislocations etc. In the present work we combined PAS with TEM and XRD to obtain complete information about microstructure of the UFG samples studied. We have found that microstructure of HPT-deformed Mg contains two kinds of regions: (a) "deformed" regions with UFG structure (grain size 100-200 nm) and high number of randomly distributed dislocations, and (b) "recrystallized" regions with low dislocation density and grain size of few microns. It indicates some kind of dynamic recovery of microstructure already during HPT processing. On the other hand, homogenous UFG structure with grain size around 100 run and high density of homogeneously distributed dislocations was formed in HPT-deformed Mg-9.33 wt.%Gd alloy. After characterization of the as-deformed microstructure the samples were subsequently isochronally annealed and the development of microstructure with increasing temperature and recovery of defects were investigated.