The magnetoelectric effects in multiferroics have a great potential in creating next-generation memory devices. We conceive a new concept of non-volatile memories based on a type of nonlinear magnetoelectric effects showing a butterfly-shaped hysteresis loop. The principle is to utilize the states of the magnetoelectric coefficient, instead of magnetization, electric polarization or resistance, to store binary information. Our experiments in a device made of the PMN-PT/Terfenol-D multiferroic heterostructure clearly demonstrate that the sign of the magnetoelectric coefficient can be repeatedly switched between positive and negative by applying electric fields, confirming the feasibility of this principle. This kind of non-volatile memory has outstanding practical virtues such as simple structure, easy operations in writing and reading, low power, fast speed, and diverse materials available.