Apparatuses, systems, methods, and computer program products are disclosed for dynamically resizing logical storage blocks. A controller for a non-volatile storage device includes a block component that determines a total number of available erase blocks of the non-volatile storage device. A controller for a non-volatile storage device includes a size module that determines numbers of erase blocks from available erase blocks to include in each of a plurality of logical blocks as a function of a total number of available erase blocks such that the numbers of erase blocks for each of the logical blocks deviates from each other by less than a predetermined deviation limit. A controller for a non-volatile storage device includes a map module that generates logical blocks for the non-volatile storage device by assigning determined numbers of erase blocks to each of the logical blocks.