AlGaN-based deep ultraviolet (DUV) multiple-quantum-wells (MQWs) incorporating strain-modulated nanostructures are proposed, demonstrating enhanced degree of polarization (DOP) and improved light extraction efficiency (LEE). The influence of Al composition and bi-axial strains on the optical behaviors of the DUV-MQWs were carefully examined. Compared with planar DUV-MQWs, strain-modulated nanostructure patterned MQWs show three times higher photoluminescence and increased DOP from -0.43 to -0.16. Moreover, nanostructure patterned DUV-MQWs under compressive strains further illustrate higher DOP and LEE values than those under tensile strains due to more efficient diffraction of the guided modes of the transverse electric (TE) polarized light. Our work demonstrates, for the first time, that a combination of compressive in-plane strain and surface nanostructure show unambiguous advantages in facilitating TE mode emission, thus have great promises in the design and optimization of highly efficient polarized DUV optoelectronic devices.