Simulating the spreading of the human immunodeficiency virus (HIV) epidemic requires a detailed description of the population network, especially for small populations in which individuals can be represented in detail and accuracy. In this paper, we introduce the concept of a complex agent network (CAN) to model the HIV epidemic by combining multi-agent systems and complex networks, in which agents represent individuals who can have sexual interactions. The applicability of CANs is demonstrated by constructing and executing a detailed HIV epidemic model for men who have sex with men (MSM) in Amsterdam, including a distinction between steady and casual relationships. We focus on MSM contacts because they play an important role in HIV epidemics and have been tracked in Amsterdam for a long time. Our experiments show good correspondence between the historical data of the Amsterdam cohort study and the simulation results.