We propose a formulation of d-dimensional SU(N) Yang-Mills theories on a d+2-dimensional space with the extra two dimensions forming a surface with non-commutative geometry. This equivalence is valid in any finite order in the 1/N expansion.