Design and exploratory synthesis of new mid-infrared (mid-IR) nonlinear optical (NLO) materials are urgently needed for modern laser science and technology because the widely used IR NLO crystals still suffer from their inextricable drawbacks. Herein, we propose a multi-level data-driven approach to realize fast and efficient structure prediction for exploration of promising mid-IR NLO materials. Techniques based on machine learning, crystal structure prediction, high-throughput calculation and screening, database building and experimental verification are tightly combined for creating pathway from chemical compositions, crystal structures to rational synthesis. Through this data-driven approach, we not only successfully predict all known structures but also find 5 thermodynamically stable and 50 metastable new selenides in A^IB^IIISe₂ systems (A^I = Li, Na, K, Rb and Cs; B^III = Al and Ga), among which 8 outstanding compounds with wide band gaps (> 2.70 eV) and large SHG responses (> 10 pm/V) are suggested. Moreover, the predicted compounds I-42d-LiGaSe₂ and I4/mcm-KAlSe₂ are successfully obtained experimentally. Especially, LiGaSe₂ exhibits a robust SHG response (≈2 × AGS) and long IR absorption edge which can cover two atmospheric windows (3-5, 8-12 μm). Simultaneously, this new research paradigm is also applicative for discovering new materials in other fields.