Sr3Au8Sn3 was synthesized through fusion of a stoichiometric amount of pure metals at 800 °C and annealing treatments at lower temperatures. Single-crystal X-ray diffraction analyses revealed that Sr3Au8Sn3 has a La3Al11-type Immm structure (a = 4.6767(8) Å, b = 9.646(2) Å, c = 14.170(2) Å, Z = 2) if annealed at 550 °C and above but a Ca3Au8Ge3-type structure (Pnnm, a = 9.6082(8) Å, b = 14.171(1) Å, c = 4.6719(4) Å, Z = 2) if annealed at 400 °C. The transition occurs at about 454 °C according to DTA data. Both structures feature columns of Sr-centered pentagonal and hexagonal prisms of Au and Sn stacked along the respective longest axial directions, but different "colorings" of the polyhedra are evident. In the high-temperature phase (Immm) all sites shared between the two prisms adopt 50:50 mixtures of Au/Sn atoms, whereas in the low-temperature phase (Pnnm) Au or Sn are completely ordered. A Klassengleiche group-subgroup relationship was established between these two structures. LMTO-ASA calculations reveal that ΔE for the disorder-to-order transformation on cooling is driven mainly by optimization of the Au-Au and Au-Sn bond populations around the former mixed Au/Sn sites, particularly those with extremely short bonds at the higher temperature. These gains also overcome the smaller effect of ordering on the entropy decrease.