We report the two-dimensional (2D) natural hetero-structure [Pb3.1Sb0.9S4][AuxTe2-x] (x = 0.52-0.36) which shows anomalous, transverse nonsaturating negative magnetoresistance (MR). For x = 0.52, the material has a commensurately modulated structure with alternating [Pb3.1Sb0.9S4] rocksalt layers and atomically thin [AuxTe2-x] sheets, as determined by single-crystal X-ray diffraction using a (3 + 1)-dimensional space group; for other x compositions, the modulated structure is absent and the Au and Te atoms are disordered. The transport properties in this system at low temperature (<100 K) are dominated by an unusual 2D hopping mechanism, while at room temperature a high carrier mobility of similar to 1352 cm(2) V-1 s(-1) obtained (x = 0.36). The confined electrons within the [AuxTe2-x] layers are also exposed to interlayer coupling with the insulating [Pb3.1Sb0.9S4] layers, and as a result, the properties of the heterostructures emerge not only from the constituent layers but also the interactions between them. Furthermore, the various Au and Te coordination patterns found in the [AuxTe2-x] sheets as a function of x further contribute to a unique electronic structure that leads to the anomalous nonsaturating negative MR with different field dependent behaviors. First-principles calculations indicate that the [AuxTe2-x] sheets are responsible for the unusual electrical transport properties in this 2D system.