Elastin is an essential vertebrate protein responsible for the elasticity of force-bearing tissues such as those of the lungs, blood vessels, and skin. One of the key features required for the exceptional properties of this durable biopolymer is the extensive covalent cross-linking between domains of its monomer molecule tropoelastin. To date, elastin's exact molecular assembly and mechanical properties are poorly understood. Here, using bovine elastin, we investigated the different types of cross-links in mature elastin to gain insight into its structure. We purified and proteolytically cleaved elastin from a single tissue sample into soluble cross-linked and non-cross-linked peptides that we studied by high-resolution MS. This analysis enabled the elucidation of cross-links and other elastin modifications. We found that the lysine residues within the tropoelastin sequence were simultaneously unmodified and involved in various types of cross-links with different other domains. The Lys-Pro domains were almost exclusively linked via lysinonorleucine, whereas Lys-Ala domains were found to be cross-linked via lysinonorleucine, allysine aldol, and desmosine. Unexpectedly, we identified a high number of intramolecular cross-links between lysine residues in close proximity. In summary, we show on the molecular level that elastin formation involves random cross-linking of tropoelastin monomers resulting in an unordered network, an unexpected finding compared with previous assumptions of an overall beaded structure.