Power-fail safe compression and dynamic capacity for a storage device in a computer system is provided. Metadata stored with each logical block in non-volatile memory in the storage device ensures that the mapping table may be recovered and stored in volatile memory for use by the computer system after power is restored to the computer system. In addition, the metadata ensures that a list of free logical block addresses written to the storage device prior to shutting down the computer system to provide access to the additional capacity that is available in the storage device by storing compressed data in the storage device may also be recovered.