Additive friction stir deposition (AFSD) of AZ31B magnesium alloy was conducted to examine evolution of grain structure, phases, and crystallographic texture. AFSD was carried out using a hollow tool made from tool steel at a constant rotational velocity of 400 rpm on the AZ31B base plate. Bar stock of AZ31B was utilized as a feed material. The linear velocity of the tool was varied in the range of 4.2-6.3 mm/s. The feed rate of the material had to be maintained at a half value compared to the corresponding linear velocity for the successful deposition. The layer thickness and length of the deposits were kept constant at 1 mm and 50 mm respectively. The tool torque and actuator force values were recorded during the process and for calculation of the average input energy for each processing condition. Temperature during the AFSD experiments was monitored using a type k thermocouple located 4 mm beneath the deposition surface at the center of the deposition track. The average input energy values showed a decreasing trend with increasing tool linear velocity. The temperature values during deposition were ∼0.7 times the liquidus of the alloy. The deposited material then was examined by laser microscope and profilometer, X-ray diffraction, scanning electron microscopy, electron back scatter diffraction (EBSC), contact angle measurement and micro hardness tests. The AFSD AZ31B samples showed reduction in areal surface roughness with an increase in the tool linear velocity. The X-ray spectra revealed increase in the intensity of prismatic planes of α-Mg phase with increase in tool linear velocity. AFSD of AZ31B Mg alloy resulted in shifting of the grain size from a broader and courser distribution within the feed material to a tighter distribution. Moreover, EBSD observations confirmed the refinement in grain size distribution as well as the presence of predominantly prismatic texture for the AFSD samples when compared to the feed material. There was a marginal improvement in the hardness for the AFSD samples compared to the feed material. However, there was no significant change in the contact angle measurements in simulated body fluid for the AFSD samples compared to the feed material. The current work demonstrated ability of AFSD technique for the additive fabrication of magnesium-based alloys and provided a methodology for examining various process attributes influencing the processing-structure-property relationship.