In this paper, we introduce a novel face recognition scheme using Local Zernike Moments (LZM). In this scheme, we follow two different approaches to construct a feature vector. In our first approach, we use Phase Magnitude Histograms (PMHs) on the complex components of LZM. In the second approach, we generate Local Zernike Xor Patterns (LZXP) by encoding the phase components, and we create gray level histograms on LZXP maps. For both of these methods, firstly, we divide images into sub-regions, then we construct the feature vectors by concatenating the histograms calculated in each of these sub-regions. The dimensionality of the feature vectors constructed in this way may be very high. So, we use a block based dimensionality reduction method, and with this method, we obtain higher performance. We evaluate our method on FERET database and achieve significant results.