A mapping table updating method, a memory control circuit unit and a memory storage device. The method includes: receiving a first data corresponding to a first logical address from a host system; loading a first logical address-physical address mapping table according to the first logical address; sending a command sequence to a rewritable non-volatile memory module; in the process of writing the first data into a first physical programming unit according to the command sequence by a control circuit of the rewritable non-volatile memory module, updating the first logical address-physical address mapping table; and after writing the first data into the first physical programming unit by the control circuit, storing the updated first logical address-physical address table back to the rewritable non-volatile memory module.