The success of Empirical Mode Decomposition (EMD) resides in its practical approach to dissect non-stationary data. EMD repetitively goes through the entire data span to iteratively extract Intrinsic Mode Functions (IMFs). This approach, however, is not suitable for data stream as the entire data set has to be reconsidered every time a new point is added. To overcome this, we propose Online EMD, an algorithm that extracts IMFs on the fly. The two key elements of Online EMD are a sliding window to compute local IMFs, and a stitching procedure to gradually append local IMFs to the final result. Using synthetic data we show that the decomposition quality of Online EMD is similar to classical EMD. We also present results obtained with a real data set to expose the practical advantages of Online EMD when dealing with data stream or large data set.