The coexistence and coupling between magnetization and electric polarization in multiferroic materials provide extra degrees of freedom for creating next-generation memory devices. A variety of concepts of multiferroic or magnetoelectric memories have been proposed and explored in the past decade. Here we propose a new principle to realize a multilevel nonvolatile memory based on the multiple states of the magnetoelectric coefficient (α) of multiferroics. Because the states of α depends on the relative orientation between magnetization and polarization, one can reach different levels of α by controlling the ratio of up and down ferroelectric domains with external electric fields. Our experiments in a device made of the PMN-PT/Terfenol-D multiferroic heterostructure confirm that the states of α can be well controlled between positive and negative by applying selective electric fields. Consequently, two-level, four-level, and eight-level nonvolatile memory devices are demonstrated at room temperature. This kind of multilevel magnetoelectric memory retains all the advantages of ferroelectric random access memory but overcomes the drawback of destructive reading of polarization. In contrast, the reading of α is nondestructive and highly efficient in a parallel way, with an independent reading coil shared by all the memory cells.