We develop a simulation toolset employing density functional theory (DFT) in conjunction with grand canonical Monte Carlo (GCMC) to study coke formation on Fe-based catalysts during propane dehydrogenation (PDH). As expected, pure Fe surfaces develop stable graphitic coke structures and rapidly deactivate. We find that coke formation is markedly less favorable on Fe₃C and FeS surfaces. Fe-Al alloys display varying degrees of coke resistance, depending on their composition, suggesting that they can be optimized for coke resistance under PDH conditions. Electronic structure analyses show that both electron-withdrawing effects (on Fe₃C and FeS) and electron-donating effects (on Fe-Al alloys) destabilize adsorbed carbon. On the alloy surfaces, a geometric effect also isolates Fe sites and disrupts the formation of graphitic carbon networks. This work demonstrates the utility of GCMC for studying the formation of disordered phases on catalyst surfaces and provides insights for improving the coke resistance of Fe-based PDH catalysts.