A method for performing storage space management, an associated data storage device, and a controller thereof are provided. The method includes: receiving an identify controller command from a host device; in response to the identify controller command, returning a reply to the host device to indicate that a plurality of logical block address (LBA) formats are supported, where the plurality of LBA formats are related to access of a non-volatile (NV) memory, and the plurality of LBA formats include a first LBA format and a second LBA format; receiving a first namespace (NS) management command from the host device; in response to the first NS management command, establishing a first NS adopting the first LBA format; receiving a second NS management command from the host device; and in response to the second NS management command, establishing a second NS adopting the second LBA format.