The titled compound K39In80 (Pearson symbol hP238) has been synthesized by fusion of the elements in stoichiometric proportions in Nb containers. The trigonal structure was established by single-crystal X-ray means (P3m1, Z = 2, a = b =17.211(2) Angstrom, c = 28.888(6) Angstrom). The crystal structure can be described as a three-dimensional indium network composed of five kinds of clusters: three types of empty In-12 icosahedra with different exo-bonding and symmetry, A (12 exo-bonds, 3m), B (12 exo-bonds, 3m), and C (6 exo-bonds, 3m); an In-16 icosioctahedron centered by a tetrahedral In atom (D, 3m); and a rather open In-15 spacer (E, 3m). This new intermediate lies between K17In41 and K22In39. Remarkably specific and transferable potassium dispositions about each cluster anion occur in the title compound as well as in K17In41 and K22In39. This characteristic makes it easier to understand the structural relationships among these three compounds, which all exhibit a common K-136 clathrate-II network of alkali metal atoms that are stuffed by cluster anions. The presence of the regular cation positions is probably decisive for the formation of all three structures. The title compound is metallic.