Following the first pioneering efforts in the 1990s that have focused on the detection of the molecular interstellar medium in high redshift galaxies, recent years have brought great advances in our understanding of the actual physical properties of the gas that set the conditions for star formation. Observations of the ground-state CO J=1-0 line have furnished crucial information on the total masses of the gas reservoirs, as well as reliable dynamical mass and size estimates. Detailed studies of rotational ladders of CO have provided insight on the temperature and density of the gas. Investigations of the very dense gas associated with actively star-forming regions in the interstellar medium, most prominently through HCN and HCO+, have enabled a better understanding of the nature of the extreme starbursts found in many high-redshift galaxies, which exceed the star formation rates of their most active present-day counterparts by an order of magnitude. Key progress in this area has been made through targeted studies of few, well-selected systems with current facilities. With the completion of the Karl G. Jansky Very Large Array and the Atacama Large (sub)Millimeter Array, it will become possible to develop a more general framework for the interpretation of these investigations based on unbiased studies of normal star-forming galaxies back to the earliest cosmic epochs.