Multivalent batteries are an energy storage technology with the potential to surpass lithium-ion batteries; however, their performance have been limited by the low voltages and poor solid-state ionic mobility of available cathodes. A computational screening approach to identify high-performance multivalent intercalation cathodes among materials that do not contain the working ion of interest has been developed, which greatly expands the search space that can be considered for material discovery. This approach has been applied to magnesium cathodes as a proof of concept, and four resulting candidate materials [NASICON V2(PO4)3, birnessite NaMn4O8, tavorite MnPO4F, and spinel MnO2] are discussed in further detail. In examining the ion migration environment and associated Mg2+ migration energy in these materials, local energy maxima are found to correspond with pathway positions where Mg2+ passes through a plane of anion atoms. While previous studies have established the influence of local coordination on multivalent ion mobility, these results suggest that considering both the type of the local bonding environment and available free volume for the mobile ion along its migration pathway can be significant for improving solid-state mobility.