In this work, we present a new approach for gender classification problem by combining two different types of local features extracted from face images. Given one input image, a Elliptical Local Binary Patterns (ELBP) operator and a Local Phase Quantization (LPQ) operator are applied to generate two pattern images. Then, each pattern image is divided into disjoint rectangular sub-regions to compute their histograms. Finally, all the histograms are concatenated to construct a global representation referred to as Combined Local Patterns (CLP) vector that contains both ELBP and LPQ patterns. In the classification stage, the binary SVM classifier is used to determine the genders of the test images. Experiments carried out upon two public databases, AR and FERET, show that our method achieves good results when dealing with gender recognition problem under facial expressions, illumination, occlusion and time-lapse variations.