New challenges in the cyber-threat domain are driven by tactical and meticulously designed Multi-Stage Attacks (MSAs). Current state-of-the-art (SOTA) Intrusion Detection Systems (IDSs) are developed to detect individual attacks through the use of signatures or identifying manifested anomalies in the network environment. However, an MSA differs from traditional one-off network attacks as it requires a set of sequential stages, whereby each stage may not be malicious when manifested individually, therefore, potentially be underestimated by current IDSs. This work proposes a new approach towards addressing this challenging type of cyber-attacks by employing external sources of information, beyond the conventional use of signatures and monitored network data. In particular, both expert knowledge and contextual information in the form of Pattern-of-Life (PoL) of the network are shown to be influential in giving an advantage against SOTA techniques. We compare our proposed anomaly-based IDS, based on decision making powered by the Dempster-Shafer (D-S) Theory and Fuzzy Cognitive Maps (FCMs), against Snort, one of the most widely deployed IDS in the world. Our results verify that the use of contextual information improves the efficiency of our IDS by enhancing the Detection Rate (DR) of MSAs by almost 50%.