Bimetallic catalytic materials are in widespread use for numerous reactions, as the properties of a monometallic catalyst are often improved upon addition of a second metal. In studies with bimetallic catalysts, it remains challenging to establish clear structure–property relationships using traditional impregnation techniques, due to the presence of multiple coexisting active phases of different sizes, shapes, and compositions. In this work, a convenient approach to prepare small and uniform Pt/Pd bimetallic nanocrystals with tailorable composition is demonstrated, despite the metals being immiscible in the bulk. By depositing this set of controlled nanocrystals onto a high-surface-area alumina support, we systematically investigate the effect of adding platinum to palladium catalysts for methane combustion. At low temperatures and in the absence of steam, all bimetallic catalysts show activity nearly identical with that of Pt/Al2O3, with much lower rates in comparison to that of the Pd/Al2O3 sample. However, unlike Pd/Al2O3, which experiences severe low-temperature steam poisoning, all Pt/Pd bimetallic catalysts maintain combustion activity on exposure to excess steam. These features are due to the influence of Pt on the Pd oxidation state, which prevents the formation of a bulk-type PdO phase. Despite lower initial combustion rates, hydrothermal aging of the Pd-rich bimetallic catalyst induces segregation of a PdO phase in close contact to a Pd/Pt alloy phase, forming more active and highly stable sites for methane combustion. Overall, this work unambiguously clarifies the activity and stability attributes of Pt/Pd phases which often coexist in traditionally synthesized bimetallic catalysts and demonstrates how well-controlled bimetallic catalysts elucidate structure–property relationships.