In a many-body localized (MBL) quantum system, the ergodic hypothesis breaks down, 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 quasiperiodic potentials along the two directions. We observe a dramatic slowing down of the relaxation for intermediate disorder strengths. Furthermore, beyond a critical disorder strength, we see negligible relaxation on experimentally accessible time scales, 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.