We experimentally study many-body localization (MBL) with ultracold atoms in a weak onedimensional 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-Andre model, which does not exhibit a singleparticle intermediate phase, in order to identify signatures of a potential many-body intermediate phase.