Understanding the collective behavior of strongly correlated electrons in materials remains a central problem in many-particle quantum physics. A minimal description of these systems is provided by the disordered Fermi-Hubbard model (DFHM), which incorporates the interplay of motion in a disordered lattice with local interparticle interactions. Despite its minimal elements, many dynamical properties of the DFHM are not well understood, owing to the complexity of systems combining out-of-equilibrium behavior, interactions, and disorder in higher spatial dimensions. Here, we study the relaxation dynamics of doubly occupied lattice sites in the three-dimensional DFHM using interaction-quench measurements on a quantum simulator composed of fermionic atoms confined in an optical lattice. In addition to observing the widely studied effect of disorder inhibiting relaxation, we find that the cooperation between strong interactions and disorder also leads to the emergence of a dynamical regime characterized by disorder-enhanced relaxation. To support these results, we develop an approximate numerical method and a phenomenological model that each capture the essential physics of the decay dynamics. Our results provide a theoretical framework for a previously inaccessible regime of the DFHM and demonstrate the ability of quantum simulators to enable understanding of complex many-body systems through minimal models.