X-ray diffraction and Raman scattering measurements, and first-principles calculations are performed to search for the formation of a NaCl-hydrogen compound. When the NaCl and H-2 mixture is laser-heated to above 1500 K at pressures exceeding 40 GPa, we observe the formation of NaClHx with P6(3)/mmc structure which accommodates H-2 molecules in the interstitial sites of the NaCl lattice forming ABAC stacking. Upon the decrease of pressure at 300 K, NaClHx remains stable down to 17 GPa. Our calculations suggest the observed NaClHx is NaCl(H-2). In addition, a hydrogen-richer phase NaCl(H-2)(4) is predicted to become stable at pressures above 40 GPa.