Complexity considerations of enterprise architectures (EA) have become an emerging topic in EA research. However, a brief look into literature reveals a great variety of complexity notions due to the lack of a precise definition. In this paper, we identify eight frequently used aspects of complexity from well-known complexity science literature and group them into four independent dimensions. Based on these, we propose a framework and simple notation to enable authors to explicitly document their interpretation of complexity. Thereby, we hope to get one step further in achieving a shared understanding of complexity in the field of EA research. In order to demonstrate the framework’s feasibility, we provide an overview of existing literature on complexity of EAs and apply the framework to explicitly document respective complexity notions. Using this approach, we were able to determine currently underrepresented notions of complexity which might be interesting for future research activities.