Standard controlled medical vocabularies are typically based on a coding scheme, while medical informatics applications tend to have a more formal conceptual foundation. When such applications attempt to use data coded with standard vocabularies, problems can arise when the standard vocabulary changes over time. A formal taxonomy is presented for describing the semantic changes which can occur in a vocabulary, such as simple addition, refinement, precoordination, disambiguation, redundancy, obsolescence, discovered redundancy, major name changes, minor name changes, code reuse, and changed codes. The taxonomy is described that used to effect change in one concept-based vocabulary (the Medical Entities Dictionary), and the utility of the approach is demonstrated by applying it to the changes appearing in the 1994 release of the International Classification of Diseases, Ninth Edition, with Clinical Modifications (ICD-9-CM).