Traditional Network Intrusion Detection Systems (NIDSs) rely on either specialized signatures of previously seen attacks, or on expensive and difficult to produce labeled traffic datasets for profiling and training. Both approaches share a common downside: they require the knowledge provided by an external agent, either in terms of signatures or as normal-operation profiles. In this paper we describe UNIDS, an Unsupervised NIDS capable of detecting 0-day attacks, i.e., network attacks for which no signature is yet available, without using any kind of signatures, labeled traffic, or training. UNIDS uses a novel unsupervised outliers detection approach based on Sub-Space Clustering and Multiple Evidence Accumulation techniques to pin-point different kinds of network intrusions and attacks such as DoS/DDoS, probing attacks, propagation of worms, buffer overflows, illegal access to network resources, etc. In this paper we make the strong point that the de-facto approach for NIDS, namely the application of rule-based detection techniques, can be highly harmful for the protected network in case of 0-day attacks. In contrast, we show how UNIDS can work as a complementary system to current NIDS to detect the occurrence of previously unseen attacks. For doing so, we compare the performance of a standard rule-based NIDS against UNIDS to detect 0-day attacks in the well-known KDD99 dataset. In addition, we also compare the performance of UNIDS against other popular unsupervised detection techniques to detect attacks in traces collected at two operation networks.