Maritime transportation plays an essential role in global trade. Due to the huge number of vessels worldwide, there is also a non-negligible volume of Maritime incidents such as collisions/sinking and illegal events (e.g., piracy, smuggling, and unauthorized fishing). Electronic equipment/systems, such as radars and Automatic Identification Systems (AIS), have contributed to improving maritime situational awareness. AIS provides one of the fundamental sources of vessel kinematics and static data. Today, many approaches are focused on automatically detecting the vessels’ traffic behavior and discovering useful patterns and deviations from those data. These studies contribute to detecting suspicious activities and anomalous trajectories, whose developed techniques could be applied in the surveillance systems, helping the authorities to anticipate proper actions. Several concerns and difficulties are involved in the analyses of vessel kinematics data: how to deal with big data generated, inconsistencies, irregular updates, dynamic data, unlabeled data, and evaluation. This article presents the approaches, constraints, and challenges in maritime traffic anomaly detection research, presenting a review, a taxonomy, and a discussion of the proposed approaches. •Several concerns are involved in the analyses of vessel kinematics data.•Manually detecting anomalous behavior is a tedious and error-prone task.•Anomaly detection is a fundamental task in different domains of knowledge.•In the maritime domain, the nonconforming patterns are referred to as anomalies.