A systematic exploration of Na- and Au-poor parts of the Na-Au-Ga system (less than 15 at. % Na or Au) uncovered several compounds with novel structural features that are unusual for the rest of the system. Four ternary compounds Na1.00(3)Au0.18Ga1.82(1) (I), NaAu2Ga4 (II), Na5Au10Ga16 (III), and NaAu4Ga2 (IV) have been synthesized and structurally characterized by single crystal X-ray diffraction: Na1.00(3)Au0.18Ga1.82(1)(I, P6/mmm, a = 15.181(2), c =9.129(2)angstrom, Z = 30); NaAu2Ga4 (II, Pnma, a = 16.733(3), b = 4.3330(9), c =7.358(3) angstrom, z = 4); Na5Au10Ga16 (III, P6(3)/m, a = 10.754(2), c =11.457(2) angstrom, Z = 2); and NaAu4Ga2 (IV, P2(1)/c, a = 8.292(2), b = 7.361(1), c =9.220(2)angstrom, beta = 116.15(3), Z = 4). Compound I lies between the large family of Bergman-related compounds and Na-poor Zintl-type compounds and exhibits a clathrate-like structure containing icosahedral clusters similar to those in cubic 1/1 approximants, as well as tunnels with highly disordered cation positions and fused Na-centered clusters. Structures II, III, and IV are built of polyanionic networks and clusters that generate novel tunnels in each that contain isolated, ordered Na atoms. Tight-binding electronic structure calculations using linear muffin-tin-orbital (LMTO) methods on II, III, IV and an idealized model of I show that all are metallic with evident pseudogaps at the Fermi levels. The integrated crystal orbital Hamilton populations for II-IV are typically dominated by Au-Ga, Ga-Ga, and Au-Au bonding, although Na-Au and Na-Ga contributions are also significant. Sodium's involvement into such covalency is consistent with that recently reported in Na-Au-M (M = Ga, Ge, Sn, Zn, and Cd) phases.