Fe-cluster-based crystal structures are predicted for chalcogenides Fe3X4 (X = S, Se, Te) using an adaptive genetic algorithm. Topologically different from the well-studied layered structures of iron chalcogenides, the newly predicted structures consist of Fe clusters that are either separated by the chalcogen atoms or connected via sharing of the vertex Fe atoms. Using first-principles calculations, we demonstrate that these structures have competitive or even lower formation energies than the experimentally synthesized Fe3X4 compounds and exhibit interesting magnetic and electronic properties. In particular, we show that Fe3Te4 can be a good candidate as a rare-earth-free permanent magnet and Fe3S4 can be a magnetic nodal-line topological material.