Abstract The evolution of the information complexity of a large database of protein sequences is investigated. The information entropy for protein sequences is determined from their algorithmic complexity and is found to change with evolutionary time at a constant rate. The information content of changed residues is always lower than the content of conserved residues. This indicates that sequences are becoming less and less random throughout evolution. It also shows that the system is being driven toward minimal complexity production. The change in information content per amino acid substitution is virtually identical for all the protein sequences studied. These results are interpreted with a statistical mechanical theory that ties sequence information to the thermodynamics of protein structure. Sequence evolution is viewed as a means to drive the system to minimise thermodynamic entropy production in a stable, non-equilibrium state. This theory provides a physical framework for understanding molecular evolution and incorporates features of both the neutralist and selectionist models.