Block matching algorithm is the most popular motion estimation technique, due to its simplicity of implementation and effectiveness. However, the algorithm suffers from a long computation time which affects its general performance. In order to achieve faster motion estimation, a new block matching algorithm based on stochastic fractal search, SFS, is proposed in this paper. SFS is a metaheuristic technique used to solve hard optimization problems in minimal time. In this work, two main contributions are presented. The first one consists of computing the motion vectors in a parallel structure as opposed to the other hierarchical metaheuristic block matching algorithms. When the video sequence frame is divided into blocks, a multi-population model of SFS is used to estimate the motion vectors of all blocks simultaneously. As a second contribution, the proposed algorithm is modified in order to enhance the results. In this modified version, four ideas are investigated. The random initialization, usually used in metaheuristics, is replaced by a fixed pattern. The initialized solutions are evaluated using a new fitness function that combines two matching criteria. The considered search space is controlled by a new adaptive window size strategy. A modified version of the fitness approximation method, which is known to reduce computation time but causes some degradation in the estimation accuracy, is proposed to balance between computation time and estimation accuracy. These ideas are evaluated in nine video sequences and the percentage improvement of each idea, in terms of estimation accuracy and computational complexity, is reported. The presented algorithms are then compared with other well-known block matching algorithms. The experimental results indicate that the proposed ideas improve the block matching performance, and show that the proposed algorithm outperforms many state-of-the-art methods.