An efficient stereo fractal video coding based on pre-searching was presented for the stereo video coding successfully. The basic stereo fractal video coding was improved by using tree structure macroblock partition, Discrete Cosine Transform(DCT) based encoding for original frame, reducing block searching range and computational repetition in advance. In stereo fractal video coding, the left view video was arranged as a main view and the Motion Compensation Prediction(MCP) was taken as coding structures by employing pre-searching limitation condition, improved UMHexagonS motion estimation algorithm, deblocking loop filter and sub-pixel block matching. The right view video was arranged as an enhanced view, the MCP and Disparity Compensation Prediction(DCP)were combined to be as coding structures, and the matching block with smallest matching error was chosen as the estimation results. In the DCP coding, a fast disparity estimation algorithm was proposed by making full use of disparity distribution restriction conditions. Experimental results indicate that the compression time by proposed stereo fractal video coding algorithm is 18%-23% that by the basic stereo fractal video coding algorithm, and the compression ratio has improved by 15.13-47.49 while a proper Peak Signal Noise Ratio(PSNR) is maintained . These results show the compression performance of the stereo fractal video coding algorithm and its applications are more flexible and practical.