We compute the effect of primordial non-Gaussianity on the halo mass function, using excursion set theory. In the presence of non-Gaussianity, the stochastic evolution of the smoothed density field, as a function of the smoothing scale, is non-Markovian and beside "local" terms that generalize Press-Schechter (PS) theory, there are also "memory" terms, whose effect on the mass function can be computed using the formalism developed in the first paper of this series. We find that, when computing the effect of the three-point correlator on the mass function, a PS-like approach which consists in neglecting the cloud-in-cloud problem and in multiplying the final result by a fudge factor sime2, is in principle not justified. When computed correctly in the framework of excursion set theory, in fact, the "local" contribution vanishes (for all odd-point correlators the contribution of the image Gaussian cancels the PS contribution rather than adding up), and the result comes entirely from non-trivial memory terms which are absent in PS theory. However it turns out that, in the limit of large halo masses, where the effect of non-Gaussianity is more relevant, these memory terms give a contribution which is the same as that computed naively with PS theory, plus subleading terms depending on derivatives of the three-point correlator. We finally combine these results with the diffusive barrier model developed in the second paper of this series, and we find that the resulting mass function reproduces recent N-body simulations with non-Gaussian initial conditions, without the introduction of any ad hoc parameter.