Complexity is an inherent attribute of any project. The purpose of defining and documenting complexity is to have an early warning tool allowing a project team to focus on certain areas and aspects of the project in order to prevent and alleviate future risks and issues caused by this complexity. The main contribution of this paper is to present a systematic view of complexity in project management by identifying its key attributes and classifying complexity by these attributes. A "complexity taxonomy", based on a survey of the existing complexity literature, is developed and discussed including the product, project, and external environment dimensions. We show how complexity types are described through simple real life examples and business cases. Then we develop a framework (tool) for applying the notion of complexity as an early warning tool for a project manager in order to timely foresee future risks and problems. The paper is intended for researchers in complexity, project management, information systems, technology solutions and business management, and also for information specialists, project managers, program managers, financial staff and technology directors.