A computer storage device having a host interface, a controller, non-volatile storage media, and firmware. The firmware instructs the controller to: store a namespace map mapping blocks of logical block addresses in a namespace to blocks from a logical address capacity of the non-volatile storage media; adjust the namespace map to change the size of the namespace; and translate logical addresses in the namespace to physical addresses for the non-volatile storage media using the namespace map.