To obtain a reliable census of the star formation rate density of the universe, it is indispensable to measure the fraction of obscured star formation up to the epoch of reionization. One method to find distant starbursts - the so-called sub millimeter galaxies (SMGs) - is via strong lensing. I am presenting results from our on-going efforts via several (sub)mm facilities to reveal and characterize the cold ISM of this source population. One outstanding result of our work is the discovery of cold molecular gas of an ultra-bright lensed SMG at z=2.04, the so-called Cosmic Eyebrow, yielding in the brightest CO() detection ever of an SMG. Its unseen brightness offers the opportunity to get new insights in the star-formation processes of high-z galaxies and thus establish it as a new reference source at z=2 for galaxy evolution. Based on our experience on blind redshift searches, I will discuss optimized strategies to determine spectroscopic redshifts via molecular gas observations of star-forming galaxies beyond z=3. Finally, I will present our IRAM NOEMA large program z-GAL aiming to determine spectroscopic redshifts of more than 100 lensed SMGs, selected from Herschel surveys, and characterize their cold molecular gas and dust properties in detail. This dataset is complemented by deep NIR imaging from the ESO public survey SHARKS.