Structural complexity of minerals is characterized using information contents of their crystal structures calculated according to the modified Shannon formula. The crystal structure is considered as a message consisting of atoms classified into equivalence classes according to their distribution over crystallographic orbits (Wyckoff sites). The proposed complexity measures combine both size- and symmetry-sensitive aspects of crystal structures. Information-based complexity parameters have been calculated for 3949 structure reports on minerals extracted from the Inorganic Crystal Structure Database. According to the total structural information content, I_{G, total}, mineral structures can be classified into very simple (0–20 bits), simple (20–100 bits), intermediate (100–500 bits), complex (500–1000 bits), and very complex (> 1000 bits). The average information content for mineral structures is calculated as 228(6) bits per structure and 3.23(2) bits per atom. Twenty most complex mineral structures are (I_{G, total} in bits): paulingite (6766.998), fantappieite (5948.330), sacrofanite (5317.353), mendeleevite-(Ce) (3398.878), bouazzerite (3035.201), megacyclite (2950.928), vandendriesscheite (2835.307), giuseppetite (2723.097), stilpnomelane (2483.819), stavelotite-(La) (2411.498), rogermitchellite (2320.653), parsettensite (2309.820), apjohnite (2305.361), antigorite (m = 17 polysome) (2250.397), tounkite (2187.799), tschoertnerite (2132.228), farneseite (2094.012), kircherite (2052.539), bannisterite (2031.017), and mutinaite (2025.067). The following complexity-generating mechanisms have been recognized: modularity, misfit relationships between structure elements, and presence of nanoscale units (clusters or tubules). Structural complexity should be distiguished from topological complexity. Structural complexity increases with decreasing temperature and increasing pressure, though at ultra-high pressures, the situation may be different. Quantitative complexity measures can be used to investigate evolution of information in the course of global and local geological processes involving formation and transformation of crystalline phases. The information-based complexity measures can also be used to estimate the 'ease of crystallization' from the viewpoint of simplexity principle proposed by J.R. Goldsmith (1953) for understanding of formation of simple and complex mineral phases under both natural and laboratory conditions. According to the proposed quantitative approach, the crystal structure can be viewed as a reservoir of information encoded in its complexity. Complex structures store more information than simple ones. As erasure of information is always associated with dissipation of energy, information stored in crystal structures of minerals must have an important influence upon natural processes. As every process can be viewed as a communication channel, the mineralogical history of our planet on any scale is a story of accumulation, storage, transmission and processing of structural information.