The crystal structures of the three high-temperature polymorphs of K3AlF6 have been solved from neutron powder diffraction, synchrotron X-ray powder diffraction, and electron diffraction data. The beta-phase (stable between 132 and 153 degrees C) and gamma-phase (stable between 153 to 306 degrees C) can be described as unusually complex superstructures of the double-perovskite structure (K2KAlF6) which result from noncooperative tilting of the AlF6 octahedra. The beta-phase is tetragonal, space group I4/m, with lattice parameters of a = 13.3862(5) angstrom and c = 8.5617(3) angstrom (at 143 degrees C) and Z = 10. In this phase, one-fifth of the AlF6 octahedra are rotated about the c-axis by similar to 45 degrees while the other four-fifths remain untilted. The large similar to 45 degrees rotations result in edge sharing between these AlF6 octahedra and the neighboring K-centered polyhedra, resulting in pentagonal bipyramidal coordination for four-fifths of the K+ ions that reside on the B-sites of the perovskite structure. The remaining one-fifth of the K+ ions on the B-sites retain octahedral coordination. The gamma-phase is orthorhombic, space group Fddd, with lattice parameters of a = 36.1276(4) angstrom, b = 17.1133(2) angstrom, and c = 12.0562(1) angstrom (at 225 degrees C) and Z = 48. In the gamma-phase, one-sixth of the AlF6 octahedra are randomly rotated about one of two directions by similar to 45 degrees while the other five-sixths remain essentially untilted. These rotations result in two-thirds of the K+ ions on the B-site obtaining 7-fold coordination while the other one-third remain in octahedral coordination. The delta-phase adopts the ideal cubic double-perovslcite structure, space group Fm (3) over barm, with a = 8.5943(1) angstrom at 400 degrees C. However, pair distribution function analysis shows that locally the delta-phase is quite different from its long-range average crystal structure. The AlF6 octahedra undergo large-amplitude rotations which are accompanied by off-center displacements of the K+ ions that occupy the 12-coordinate A-sites.