With frequent flaring activity of its relativistic jets, Cygnus X-3 is one of the most active microquasars and is the only Galactic black hole candidate with confirmed high energy Gamma-ray emission, thanks to detections by Fermi/LAT and AGILE. In 2011, Cygnus X-3 was observed to transit to a soft X-ray state, which is known to be associated with high-energy Gamma-ray emission. We present the results of a multi-wavelength campaign covering a quenched state, when radio emission from Cygnus X-3 is at its weakest and the X-ray spectrum is very soft. A giant (~ 20 Jy) optically thin radio flare marks the end of the quenched state, accompanied by rising non-thermal hard X-rays. Fermi/LAT observations (E >100 MeV) reveal renewed Gamma-ray activity associated with this giant radio flare, suggesting a common origin for all non-thermal components. In addition, current observations unambiguously show that the Gamma-ray emission is not exclusively related to the rare giant radio flares. A 3-week period of Gamma-ray emission is also detected when Cygnus X-3 was weakly flaring in radio, right before transition to the radio quenched state. No Gamma rays are observed during the ~ one-month long quenched state, when the radio flux is weakest. Our results suggest transitions into and out of the ultrasoft X-ray (radio quenched) state trigger Gamma-ray emission, implying a connection to the accretion process, and also that the Gamma-ray activity is related to the level of radio flux (and possibly shock formation), strengthening the connection to the relativistic jets.