Assigning functions to the vast array of proteins present in eukaryotic cells remains challenging. To identify relationships between proteins, and thereby enable functional annotation of proteins, we determined changes in abundance of 10,323 human proteins in response to 294 biological perturbations using isotope-labeling mass spectrometry. We applied the machine learning algorithm treeClust to reveal functional associations between co-regulated human proteins from ProteomeHD, a compilation of our own data and datasets from the Proteomics Identifications database. This produced a co-regulation map of the human proteome. Co-regulation was able to capture relationships between proteins that do not physically interact or colocalize. For example, co-regulation of the peroxisomal membrane protein PEX11β with mitochondrial respiration factors led us to discover an organelle interface between peroxisomes and mitochondria in mammalian cells. We also predicted the functions of microproteins that are difficult to study with traditional methods. The co-regulation map can be explored at www.proteomeHD.net .