We introduce block versions of the multielimination incomplete LU (ILUM) factorization preconditioning technique for solving general sparse unstructured linear systems. These preconditioners have a multilevel structure and, for certain types of problems, may exhibit properties that are typically enjoyed by multigrid methods. Several heuristic strategies for forming blocks of independent sets are introduced and their relative merits are discussed. The advantages of block ILUM over point ILUM include increased robustness and efficiency. We compare several versions of the block ILUM, point ILUM, and the dual-threshold-based ILUT preconditioners. In particular, tests with some convection-diffusion problems show that it may be possible to obtain convergence that is nearly independent of the Reynolds number as well as of the grid size.