Multivalent batteries are an energy storage technology with the potential to surpass lithium-ion batteries, however their performance has 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 materials discovery. This approach has been applied to magnesium cathodes as a proof of concept and resulting candidate materials 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 works have established the influence of local coordination on multivalent ion mobility, these results suggest that considering both the type of local bonding environment as well as available free volume for the mobile ion along its migration pathway can be significant for improving solid-state mobility.