We experimentally study many-body localization (MBL) with ultracold atoms in a weak one-dimensional quasiperiodic potential, which in the noninteracting limit exhibits an intermediate phase that is characterized by a mobility edge. We measure the time evolution of an initial charge density wave after a quench and analyze the corresponding relaxation exponents. We find clear signatures of MBL, when the corresponding noninteracting model is deep in the localized phase. We also critically compare and contrast our results with those from a tight-binding Aubry-Andr{e} model, which does not exhibit a single-particle intermediate phase, in order to identify signatures of a potential many-body intermediate phase.