This paper presents a bimodal biometric recognition system based on the extracted features of the human palmprint and iris using a new graph-based approach termed Fisher locality preserving projections (FLPP). This new technique employs two graphs with the first being used to characterize the within-class compactness and the second dedicated to the augmentation of the between-class separability. By applying the FLPP, only the most discriminant and stable palmprint and iris features are retained. FLPP was implemented on the frequency domain by transforming the extracted region of interest extraction of both biometric modalities using Fourier transform. Subsequently, the palmprint and iris features vectors obtained are matched with their counterpart in the templates databases and the obtained scores are fused to produce a final decision. The proposed combination of palmprint and iris patterns has shown an excellent performance compared to unimodal palmprint biometric recognition. The system was evaluated on a database of 108 subjects and the experimental results show that our system performs very well and achieves a high accuracy expressed by an equal error rate of 0.00%.