Submerged friction-stir welding (SFSW) underwater and under liquid nitrogen is demonstrated as an alternative and improved method for creating fine-grained welds in dissimilar metals. Plates of AZ31 (Mg alloy) and AA5083 H34 were joined by friction-stir welding in three different environments, i.e., in air, water, and liquid nitrogen at 400 rpm and 50 mm/min. The temperature profile, microstructure, scanning electron microscopy (SEM)-energy-dispersive spectroscopy (EDS) analysis, X-ray diffraction (XRD), hardness, and tensile testing results were evaluated. In the stir zone of an air-welded specimen, formation of brittle intermetallic compounds of Al3Mg2, Al12Mg17, and Al2Mg3 contributed to cracking in the weld nugget. These phases were formed because of constitutional liquation. Friction-stir welding underwater and under liquid nitrogen significantly suppresses the formation of intermetallic compounds because of the lower peak temperature. Furthermore, the temperature profiles plotted during this investigation indicate that the largest amount of a dagger T is generated by the weld under liquid nitrogen, which is performed at the lowest temperature. It is shown that in low-temperature FSW, the flow stress is higher, plastic contribution increases, and so adiabatic heating, a result of high strain and high strain-rate deformation, drives the recrystallization process beside frictional heat.