Let $G$ be an unramified group over a $p$ -adic field $F$ , and let $E/F$ be a finite unramified extension field. Let $\theta$ denote a generator of ${\rm Gal}(E/F)$ . This article concerns the matching, at all semisimple elements, of orbital integrals on $G(F)$ with $\theta$ -twisted orbital integrals on $G(E)$ . More precisely, suppose that $\phi$ belongs to the center of a parahoric Hecke algebra for $G(E)$ . This article introduces a base change homomorphism $\phi \mapsto b\phi$ taking values in the center of the corresponding parahoric Hecke algebra for $G(F)$ . It proves that the functions $\phi$ and $b\phi$ are associated in the sense that the stable orbital integrals (for semisimple elements) of $b\phi$ can be expressed in terms of the stable twisted orbital integrals of $\phi$ . In the special case of spherical Hecke algebras (which are commutative), this result becomes precisely the base change fundamental lemma proved previously by Clozel [Cl4] and Labesse [L1]. As has been explained in [H1], the fundamental lemma proved in this article is a key ingredient for the study of Shimura varieties with parahoric level structure at the prime $p$