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, a multi-level data-driven approach to realize fast and efficient structure prediction for the exploration of promising mid-IR NLO materials is proposed. Techniques based on machine learning, crystal structure prediction, high-throughput calculation and screening, database building, and experimental verification are tightly combined for creating pathways from chemical compositions, crystal structures to rational synthesis. Through this data-driven approach, not only are all known structures successfully predicted but also five thermodynamically stable and 50 metastable new selenides in A(I)B(III)Se(2) systems (A(I) = Li, Na, K, Rb, and Cs; B-III = Al and Ga) are found, among which eight outstanding compounds with wide bandgaps (> 2.70 eV) and large SHG responses (>10 pm V-1) are suggested. Moreover, the predicted compounds I4 over bar 2d-LiGaSe2 and I4/mcm-KAlSe2 are successfully obtained experimentally. In particular, LiGaSe2 exhibits a robust SHG response (approximate to 2 x AGS) and long IR absorption edge that can cover two atmospheric windows (3-5, 8-12 mu m). Simultaneously, this new research paradigm is also applicative for discovering new materials in other fields.