AbstractMixed‐anion compounds have attracted growing attentions, but their synthesis is challenging, making a rational search desirable. Here, we explored LaF₃‐LaX₃ (X=Cl, Br, I) system using ab initio structure searches based on evolutionary algorithms, and predicted LaF₂X and LaFX₂ (X=Br, I), which are respectively isostructural with LaHBr₂ and YH₂I, consisting of layered La‐F blocks with single and double ordered honeycomb lattices, separated by van der Waals gaps. We successfully synthesized these compounds: LaF₂Br and LaFI₂ crystallize in the predicted structure, while LaF₂I is similar to the predicted one but with different layer stacking. LaF₂I exhibits fluoride ion conductivity comparable to that of non‐doped LaF₃, and has the potential to show better ionic conductivity upon appropriate doping, given the theoretically lower diffusion energy barrier and the presence of soft iodine anions. This study shows the structure prediction using evolutionary algorithms will accelerate the discovery of mixed‐anion compounds in future, in particular those with an ordered anion arrangement.