We study the first non-planar correction to gluon scattering amplitudes in N=4 SYM theory. The correction takes the form of a double trace partial amplitude and is suppressed by one power of 1/N with respect to the leading single trace contribution. We extend the duality between planar scattering amplitudes and null polygonal Wilson loops to the double trace amplitude. The new duality relates the amplitude to the correlation function of two infinite null polygonal Wilson lines that are subject to a quantum periodicity constraint. We test the duality perturbatively at one-loop order and demonstrate it for the dual string in AdS. The duality allows us to extend the notion of the loop integrand beyond the planar limit and to determine it using recursion relations. It also allows us to apply the integrability-based pentagon operator product expansion approach to the first non-planar order. This was the original motivation for this work and it will be reported on in a separate publication.