This paper presents a novel fast mode decision algorithm for H.264/AVC based on a Pareto-optimal macroblock classification strategy. Previously published H.264 low complexity schemes mostly concentrated on improving class decision metrics, but did not justify the choice of MD classes. Herein, we use Pareto analysis to derive the optimal set of MD classes and to define efficient class decision metrics. For each MD class only rate-distortion optimal complexity settings are used. Experimental results show that the proposed algorithm outperforms previously published algorithms, providing a 57-73% reduction in total computational complexity with some reduction in bit rate and acceptable visual quality.