Formaldehyde is a widely used fixative in biology and medicine. The current chemical model for formaldehyde cross-linking of proteins is the formation of a methylene bridge that incorporates one carbon atom into the link. Here, we present mass spectrometry data that largely refute this model. Instead, our data show that cross-linking of structured proteins mainly involves a reaction that incorporates two carbon atoms into the link. Under MS/MS fragmentation, the link cleaves symmetrically to yield unusual fragments with a modification of one carbon atom. We apply this new understanding of the underlying cross-linking chemistry to the structural approach of cross-linking coupled to mass spectrometry. First, we cross-linked a mixture of purified proteins with formaldehyde. Our new analysis readily identified tens of cross-links from these proteins, which fit well with their atomic structures. We then perform in-situ cross-linking of human cells in culture. We identified 469 intra-protein and 90 inter-protein cross-links, which also fit well with available atomic structures. Interestingly, many of these cross-links could not be mapped onto a known structure and thus provide new structural insights. We highlight an example in which formaldehyde cross-links localize the binding site of βNAC on the ribosome. We also find several interactions of actin with auxiliary proteins. Our findings not only expand our understanding of formaldehyde reactivity and toxicity, but also clearly demonstrate how to use this potent reagent for structural studies.