We propose an efficient fractal video coding algorithm that exploits the correlation between range cubes. Four domain cubes mapped by the previous neighboring range cubes are considered as the good candidates for the input range cube. Two search methods, which take advantage of the correlation between intercubes in the spatial and spatial-temporal directions, are developed to reduce the computational complexity in the encoding phase. In order to raise the compression efficiency, a search-order coding technique is applied to encode the candidate domain cubes. Simulation results show that when the proposed method is implemented with a fast fractal video coding algorithm, it can further reduce the encoding times and bit rate with insignificant loss of video quality.