A non-volatile semiconductor storage device according to an embodiment includes: a memory cell array including an array of electrically rewritable memory cells and configured to be able to store N bits of data (where N is a natural number not less than 2) in one memory cell; and a controller operative to control read, write and erase operations of the memory cell array. The memory cell array includes a first region having a first memory cell operative to retain N bits of data, and a second region having a second memory cell operative to retain M bits of data (where M is a natural number less than N). A data structure of address data received by the controller when accessing the first memory cell is the same as a data structure of address data received from the outside when accessing the second memory cell.