Magnesium (Mg) is one of the lightest industrially used metals. However, wide applications of Mg-based components require a substantial enhancement of their mechanical characteristics. This can be achieved by introducing small particles or fibers into the metal matrix. Using first-principles calculations, we investigate the stability and mechanical properties of a nanocomposite made of magnesium reinforced with boron nitride (BN) nanostructures (BN nanotubes and BN monolayers). We show that boron vacancies at the BN/Mg interface lead to a substantial increase in BN/Mg bonding establishing an efficient route towards the development of BN/Mg composite materials with enhanced mechanical properties.