In this article we describe the design and construction of a laboratory astrophysics experiment that recreates the harsh conditions of the Interstellar Medium (ISM) and is used to study the heterogeneous chemistry that occurs there. The Nottingham Surface Astrophysics Experiment is used to determine, empirically, accurately, and usually for the first time, key physical and chemical constants that are vital for modeling and understanding the ISM. It has been designed specifically to investigate gas-solid interactions under interstellar conditions. The pressure regime is ideally matched to molecular densities in dusty disks in protostellar or protoplanetary regions. The ultrahigh vacuum system is routinely capable of obtaining pressures that are only three orders of magnitude above those in the ISM, with similar relative concentrations of the two most abundant gases in such regions, H-2 and CO, and an absence of any other major gas components. A short introduction describes the astronomical motivation behind this experiment. In Sec. II we then give details of the design, construction, and calibration of each component of the experiment. The cryostat system has far exceeded design expectations, and reaches temperatures between 7 and 500 K. This is comparable with the ISM, where dust temperatures from 10 K have been observed. Line-of-sight mass spectrometry, reflection absorption infrared spectroscopy, and quartz crystal microbalance mass measurements were combined into a single instrument for the first time. The instrument was carefully calibrated, and its control and data acquisition system was developed to ensure that experimental parameters are recorded as accurately as possible. In Sec. III we present some of the experimental results from this system that have not been published elsewhere. The results presented here demonstrate that the system can be used to determine desorption enthalpies, Delta(des)H, bonding systems, and sticking probabilities between a variety of gases and ices common to the ISM. This instrument will greatly facilitate our understanding of surface processes that occur in the ISM, and allow us to investigate "mimic" ISM systems in a controlled environment. In this article we illustrate that laboratory surface astrophysics is an exciting and emerging area of research, and this instrument in particular will have a major impact through its contributions to both surface science and astronomy.