We extend the sequential data assimilation methodology to the case where the probability of errors and noises are distributed according to not only Gaussian but power and Lévy laws with heavy tails. The main tool required to solve this ``Kalman-Lévy'' filter is the ``tail-covariance'' matrix. It is a natural generalization of the covariance matrix which is mathematically ill-defined when the exponents of the power law correspodns to the heavy tail regime. We present the full solution for the Kalman-Lévy filter and discuss its properties on pedagogical examples. The standard Kalman-Gaussian filter is recovered as a special case when the exponent equals 2 The optimal Kalman-Lévy filter is found to differ substantially from the standard Kalman-Gaussian filter as the exponent deviates from $2$. For smaller exponents, error forecast by the Kalman-Lévy filter in terms of the tail-covariance matrix result in less growth for divergent (unstable) dynamics and less decay for convergent (stable) dynamics. Furthermore the Kalman-Lévy gain for optimization using the forecast and observed variables favors more strongly the best of the two as estimated from the tail-covariance matrix. Our theory also estimates the error caused by the standard Kalman-Gaussian filter when it is applied to the system with heavy tail probability distribution. Direct numerical experiments confirms our theoretical predictions. We also discuss implication of heavy-tail stochastic noises to forecast skill for atmospheric low-frequency variability.