Automatic segmentation methods are important tools for quantitative analysis of magnetic resonance images. Recently, patch-based label fusion approaches demonstrated state-of-the-art segmentation accuracy. In this paper, we introduce a new patch-based method using the PatchMatch algorithm to perform segmentation of anatomical structures. Based on an Optimized PAtchMatch Label fusion (OPAL) strategy, the proposed method provides competitive segmentation accuracy in near real time. During our validation on hippocampus segmentation of 80 healthy subjects, OPAL was compared to several state-of-the-art methods. Results show that OPAL obtained the highest median Dice coefficient (89.3%) in less than 1 sec per subject. These results highlight the excellent performance of OPAL in terms of computation time and segmentation accuracy compared to recently published methods.