We employ high-temperature ab initio molecular dynamics (AIMD) as a sampling approach to discover low-energy, semiconducting, indium phosphide nanostructures. Starting from undercoordinated models of InP (e.g., a single layer of InP(111)), rapid rearrangement into a stabilized, higher-coordinate but amorphous cluster is observed across the size range considered (In3P3 to In22P22). These clusters exhibit exponential decrease in energy per atom with system size as effective coordination increases, which we define through distance-cutoff coordination number assignment and partial charge analysis. The sampling approach is robust to initial configuration choice, as consistent results are obtained when alternative crystal models or computationally efficient generation of structures from sequential addition and removal of atoms are employed. This consistency is observed across the 66 structures compared here, and even when as many as five approaches are compared, the average difference in energy per pair of atoms in these structures is only 1.5 kcal/mol at a given system size. Interestingly, the energies of these amorphous clusters are lower than geometry optimized spherical models of bulk InP typically used for simulations of quantum dots. Favorable energetics appear correlated to highly coordinated indium and phosphorus with coordination numbers up to 5 and 7, respectively, as well as formation of phosphorus–phosphorus bonds.