The exploration on novel arsenide infrared (IR) nonlinear optical (NLO) crystals remains a central challenge due to the lack of rational structure design strategies. By adding phase strategy, we successfully synthesized two new non-centrosymmetric arsenides BaGa2Si7As12 (BGSA) and BaIn2Si7As12 (BISA) with tetrahedra-ordered BaSi7P10 as a template phase. BGSA and BISA exhibits giant SHG responses (2.6 and 3.7 × ZGP), broad IR transparency range (cutoff edge up to 12.2 μm), and moderate birefringence (0.077 and 0.096), indicating they are potential long-wave IR NLO materials. They represent the first successful synthesis of tetrahedra-ordered arsenides of A-M-As system. First-principles calculations reveal that both BGSA and BISA achieve a concurrent enhancement in both the NLO coefficients and the band gaps compared to the hypothetical BaSi7As10 (the isomorphism to BaSi7P10). The enhanced NLO coefficients are attributed to the elevated F × n/V, the product of the average flexibility and density of the tetrahedral groups. The enlarged band gaps are attributed to the increased average coordination number of the As atoms.