In this work we elaborate the effect of grain size on the sensitivity of chemo-resistive metal-oxide gas sensors with nanosized grains. The effective carrier concentration in nanocrystalline SnO2 sensors with various grain sizes is calculated as a function of the surface state density. This involves numerical computation of the charge balance equation (i.e., the electroneutrality condition) using approximated analytical solutions of Poisson's equation for small spherical crystallites. The calculations demonstrate a sharp decrease in the carrier concentration when the surface state density reaches a critical value that corresponds to a condition of fully depleted grains, namely when nearly all the electrons are trapped at the surface. Assuming that the variations in the surface state density are induced by surface interactions with the gas phase, these calculations enable to simulate the response curves of nanocrystalline SnO2 gas sensors. The simulations show that the conductivity increases linearly with decreasing trapped charge densities, and that the sensitivity to the gas-induced variations in the trapped charge density is proportional to 1/D, where D is the average grain size.