Multi-dimensional outlier detection (MOD) over data streams is one of the most significant data stream mining techniques. When multivariate data are streaming in high speed, outliers are to be detected efficiently and accurately. Conventional outlier detection method is based on observing the full dataset and its statistical distribution. The data is assumed stationary. However, this conventional method has an inherent limitation-it always assumes the availability of the entire dataset. In modern applications, especially those that operate in the real time environment, the data arrive in the form of live data feed; they are dynamic and ever evolving in terms of their statistical distribution and concepts. Outlier detection should no longer be done in batches, but in incremental manner. In this chapter, we investigate into this important concept of MOD. In particular, we evaluate the effectiveness of a collection of incremental learning algorithms which are the underlying pattern recognition mechanisms for MOD. Specifically, we combine incremental learning algorithms into three types of MOD-Global Analysis, Cumulative Analysis and Lightweight Analysis with Sliding Window. Different classification algorithms are put under test for performance comparison.