A series of steady-state and short-term experiments on a three-phase circulating-bed biofilm reactor (CBBR) for removing toluene from gas streams were conducted to investigate the effect of macroporous-carrier size (1-mm cubes versus 4-mm cubes, which have the same total surface area) on CBBR performance. Experimental conditions were identical, except for the carrier size. The CBBR with 1-mm carriers (the 1-mm CBBR) overcame the performance limitation observed with the CBBR with 4-mm carriers (the 4-mm CBBR): oxygen depletion inside the biofilm. The 1-mm CBBR consistently had the superior removal efficiencies of toluene and COD, higher than 93% for all, and the advantage was greatest for the highest toluene loading, $0.12;M/m^2-day$. The 1-mm carriers achieved superior performance by minimizing the negative effects of oxygen depletion, because they had 4.7 to 6.8 times thinner biofilm depths. The 1-mm carriers continued to provide protection from excess biomass detachment and inhibition from toluene. Finally, the 1-mm CBBR achieved volumetric removal capacities up to 300 times greater than demonstrated by other biofilters treating toluene and related volatile hydrocarbons.