In a many-body localized (MBL) quantum system, the ergodic hypothesis breaks down completely, giving rise to a fundamentally new many-body phase. Whether and under which conditions MBL can occur in higher dimensions remains an outstanding challenge both for experiments and theory. Here, we experimentally explore the relaxation dynamics of an interacting gas of fermionic potassium atoms loaded in a two-dimensional optical lattice with different quasi-periodic potentials along the two directions. We observe a dramatic slowing down of the relaxation for intermediate disorder strengths and attribute this partially to configurational rare-region effects. Beyond a critical disorder strength, we see negligible relaxation on experimentally accessible timescales, indicating a possible transition into a two-dimensional MBL phase. Our experiments reveal a distinct interplay of interactions, disorder, and dimensionality and provide insights into regimes where controlled theoretical approaches are scarce.