Several embodiments of memory devices and related methods for initializing such memory devices based on initialization information on stored in NAND-based memory media. In one embodiment, a memory device can include a controller operably coupled to the memory media. The controller is configured to determine whether the initialization information stored at a region of the memory media is valid, initialize the memory device based at least in part on the initialization information when valid, and invalidate the initialization information stored at the region of the memory media by writing to the region of the memory media without first erasing the region of the memory media.