In this work we propose a novel spatial knowledge discovery pipeline capable of automatically unravelling the “roads of the sea” and maritime traffic patterns by analysing voluminous vessel tracking data, as collected through the Automatic Identification System (AIS). We present a computationally efficient and highly accurate solution, based on a MapReduce approach and unsupervised learning methods, capable of identifying the spatiotemporal dynamics of ship routes and most crucially their characteristics, thus deriving maritime “patterns of life” at a global scale, without the reliance on any additional information sources or a priori expert knowledge. Experimental results confirm high accuracy of results and superior performance in comparison to other methods, with the entire processing duration completing in less than 3 hours for more than a terabyte of non-uniform spatial data. Finally, to clearly demonstrate the applicability and impact of our proposed method, we evaluate its ability to detect real world “anomalies”, such as maritime incidents reported in the European Marine Casualty Information Platform. Numerical results show the advantages of our scheme in terms of accuracy, with an achieved anomaly detection accuracy of higher than 93%, by detecting 313 out of 335 relevant maritime incidents.