Genetic algorithm searches based on a cluster expansion model are performed to search for stable phases of Fe-V-Si ternary. We identify a new thermodynamically, dynamically and mechanically stable ternary phase of Fe5V2Si with 2 formula units in a tetragonal unit cell. The formation energy of this new ternary phase is −36.9 meV/atom below the current ternary convex hull. The magnetic moment of Fe in the new structure varies from −0.30–2.52 μB depending strongly on the number of Fe nearest neighbors. The total magnetic moment is 10.44 μB/unit cell for new Fe5V2Si structure and the system is ordinarily metallic.