The　intrinsic　independent　features　of　the　optimal　codebook　cubes　searching　process　in　fractal　video　compression　systems　are　examined　and　exploited.　The　design　of　a　suitable　parallel　algorithm　reflecting　the　concept　is　presented.　The　Message　Passing　Interface　(MPI)　is　chosen　to　be　the　communication　tool　for　the　implementation　of　the　parallel　algorithm　on　distributed　memory　parallel　computers.　Experimental　results　show　that　the　parallel　algorithm　is　able　to　reduce　the　compression　time　and　achieve　a　high　speed-up　without　changing　the　compression　ratio　and　the　quality　of　the　decompressed　image.　A　scalability　test　was　also　performed,　and　the　results　show　that　this　parallel　algorithm　is　scalable.