A semiconductor memory device includes first memory cell transistors, a memory block, and word lines. Each of the first memory cell transistors has a stacked gate including a charge accumulation layer and a control gate and is capable of holding M bits (M≠2i, where i is a natural number and M is a natural number greater than or equal to 3) of data. The memory block includes the first memory cell transistors and is erase unit of the data. The data held in the first memory cell transistors included in the memory block is erased simultaneously. The size of data the memory block is capable of holding is L bits (L=2k, where k is a natural number). The word lines connect in common the control gates of the first memory cell transistors.