Until the announcement of NIST's AES contest, the majority of block ciphers followed the example of the DES in using a block size of 64 bits (8 bytes). However the Birthday paradox tells us that after accumulating a number of blocks equal to the square root of the total number possible, there will be an approximately 50% chance of two or more being the same, which would start to leak information about the message contents. Thus even when used with a proper encryption mode, only B = 32 GB of data can be safely sent under one key. In practice we want odds a lot better than 50%, so we are restricted to much less data - say a few hundred megabytes. Once that seemed like a fair amount of data, but today it is easily exceeded. (If the cipher mode does not properly randomise the input, the limit is even worse).

Consequently AES candidates were required to support a block length of 128 bits (16 bytes). This should be acceptable for up to B = 256 exaBytess of data. That should be enough for quite a few years to come.

A few block ciphers, such as RC5, actually support a variable block size, while Joan Daemen's 3-Way has a 96 bit block.

The Luby-Rackoff construction and the Outerbridge construction can both increase the effective block size of a cipher.