The standard model of physics does not require the fundamental constants of nature (the FCs) to be constant in space and time. In the past, quests to measure possible variations have mostly been performed with atomic and also molecular hydrogen as well as metal absorption lines at (observer frame) optical wavelengths. At (sub)millimeter and radio wavelengths, in various cases dramatically different dependences of certain spectral lines on FCs allow for extremely sensitive constancy tests. Farthest back in time, to 12.8 Gyr, reach our recent sensitive limits on a combination of the fine structure constant and the proton-to-electron mass ratio, that we determined from sensitive measurements of emission from rotational CO and fine structure lines from atomic or ionized carbon toward high redshift (up to z = 6.4) quasar host galaxies. We shall briefly summarize these but shall concentrate on absorption line measurements, which are much more sensitive. At present, 5 (sub)mm- and/or radio-wavelength molecular line absorbers are known at cosmological distances, all at z < 0.9 and thus probing look back times up to about 7 Gyr. Three of these are the lensing galaxies of graviations lens systems. Observations of numerous different molecules toward on of these systems not only delivers the tighest cosmological limits on the proton-to-electron mass to date but also reveal a fasciating astrochemistry that is quite different from that of the Milky Way’s interstellar medium. We shall also provide an outlook on opportunities with the ALMA, the JVLA and the SKA.