We derive, within the Hamiltonian formalism, the classical exchange algebra of a lambda deformed string sigma model in a symmetric space directly from a 4d holomorphic Chern-Simons theory. The explicit forms of the extended Lax connection and R-matrix entering the Maillet bracket of the lambda model are explained from a symmetry principle. This approach, based on a gauge theory, may provide a mechanism for taming the non-ultralocality that afflicts most of the integrable string theories propagating in coset spaces.