In excursion set theory, the computation of the halo mass function is mapped into a first-passage time process in the presence of a barrier, which in the spherical collapse model is a constant and in the ellipsoidal collapse model is a fixed function of the variance of the smoothed density field. However, N-body simulations show that dark matter halos grow through a mixture of smooth accretion, violent encounters, and fragmentations, and modeling halo collapse as spherical, or even as ellipsoidal, is a significant oversimplification. In addition, the very definition of what is a dark matter halo, both in N-body simulations and observationally, is a difficult problem. We propose that some of the physical complications inherent to a realistic description of halo formation can be included in the excursion set theory framework, at least at an effective level, by taking into account that the critical value for collapse is not a fixed constant δ c , as in the spherical collapse model, nor a fixed function of the variance σ of the smoothed density field, as in the ellipsoidal collapse model, but rather is itself a stochastic variable, whose scatter reflects a number of complicated aspects of the underlying dynamics. Solving the first-passage time problem in the presence of a diffusing barrier we find that the exponential factor in the Press-Schechter mass function changes from exp{–δ2 c /2σ2} to exp{–aδ2 c /2σ2}, where a = 1/(1 + DB ) and DB is the diffusion coefficient of the barrier. The numerical value of DB , and therefore the corresponding value of a, depends among other things on the algorithm used for identifying halos. We discuss the physical origin of the stochasticity of the barrier and, from recent N-body simulations that studied the properties of the collapse barrier, we deduce a value DB 0.25. Our model then predicts a 0.80, in excellent agreement with the exponential fall off of the mass function found in N-body simulations, for the same halo definition. Combining this result with the non-Markovian corrections computed in Paper I of this series, we derive an analytic expression for the halo mass function for Gaussian fluctuations and we compare it with N-body simulations.