In hot non-Abelian gauge theories, processes characterized by the momentum scale g(2)T (such as electroweak baryon number violation in the very early universe) are non-perturbative, An effective theory for the soft (\p\ similar to g(2)T) field modes is obtained by integrating out momenta larger than g(2)T. Starting from the hard thermal loop effective theory, which is the result of integrating out the scale T, it is shown how to integrate wt the scale gT in an expansion in the gauge coupling g. At leading order in g, one obtains Vlasov-Boltzmann equations for the soft field modes, which contain a Gaussian noise and a collision term. The 2-point function of the noise and the collision term are explicitly calculated in a leading logarithmic approximation. In this approximation the Boltzmann equation is solved. The resulting effective theory for the soft held modes is described by a Langevin equation. It determines the parametric form of the hot baryon number violation rate as Gamma = kappa g(10) log(1/g)T-4, and it allows for a calculation of kappa on the lattice. (C) 1999 Elsevier Science B.V. All rights reserved.