Standardized business documents are a prerequisite for successful information exchange in electronic business transactions. The United Nations Centre for Trade Facilitation and eBusiness (UN/CEFACT) provides a conceptual modeling approach, called Core Components, used by Business Partners (BPs) for defining business document models (BDMs). BDMs are essential for defining service interfaces in service-oriented systems. However, in such a highly dynamic environment with ever-changing market demands, BPs are confronted with the need to revise their BDMs resulting in a multitude of different versions. BPs may dictate the use of new versions of BDMs, but small- and medium-sized enterprises (SMEs) may not always adopt new BDM versions due to the cost and effort involved, inhibiting automated electronic information exchange. In this article, we propose a framework including (i) a classification of the impact of changes in BDMs, (ii) evolution templates for the automated transformation of business documents between different BDM versions, and (iii) mitigation strategies for evolutions where fully-automated and semantic-preserving transformations are not feasible. Having such a framework at hand provides SMEs with a low-cost and light-weight approach for dealing with evolving market requirements and hence evolving business documents. Finally, we analyze the evolution of UN/CEFACT's Cross Industry Invoice which has been mandated to be used for electronic invoicing within the European Union as well as present a critical discussion of the evolution templates defined.