BOREXINO has set new standards in the field of ultra-low background experiments. Such a success was only possible by a strict quality control program during the construction phase of the experiment. In this paper, we describe how construction materials and auxiliary systems of the BOREXINO detector were screened for their residual radioactivity with unprecedented high sensitivity. The highly sensitive assay techniques developed for this purpose were also used to validate the purity of water and nitrogen used in the experiment. Moreover, we report on the production of 222Rn-free nitrogen and synthetic air with very low 222Rn concentration as well as on the successful search for commercial nitrogen with a particularly low concentration of argon and krypton.