We introduce a new multimode cavity QED architecture for superconducting circuits that can be used to implement photonic memories, more efficient Purcell filters, and quantum simulations of photonic materials. We show that qubit interactions mediated by multimode cavities can have exponentially improved contrast for two qubit gates without sacrificing gate speed. Using two qubits coupled via a three-mode cavity system we spectroscopically observe multimode strong couplings up to 102 MHz and demonstrate suppressed interactions off resonance of 10 kHz when the qubits are ≈600MHz detuned from the cavity resonance. We study Landau-Zener transitions in our multimode systems and demonstrate quasiadiabatic loading of single photons into the multimode cavity in 25 ns. We introduce an adiabatic gate protocol to realize a controlled-Z gate between the qubits in 95 ns and create a Bell state with 94.7% fidelity. This corresponds to an on/off ratio (gate contrast) of 1000.