A method of tonally stabilizing a video sequence is provided herein. The method includes the following stages: automatically selecting one or more anchor frames from a sequence of frames; obtaining an anchor adjustment map for each selected anchor frame; applying an edge-preserving smoothing algorithm to the sequence of frames; generating for any given pair of smoothed frames, a robust set of pixels indicating pixels affected by external tonal fluctuation only; initializing an adjustment map for any given frame by applying the anchor adjustment map to accumulated color differences between pixels of the robust set of the given frame and the anchor frame; and completing the initialized adjustment map by predicting values of pixels in each adjustment map not included in the robust set by applying an interpolation at a color space for these pixels, wherein the adjustment maps are usable for tonally aligning the video sequence with the anchor frame.