Protein and DNA polymorphisms were surveyed among seven accessions of wild fenugreek (Trigonella foenum-graecum L.) to estimate their genetic diversity and relationships. Samples were obtained from diverse ecogeographical areas in Saudi Arabia and Yemen. Sodium dodecyl sulfate-polyacrylamide gel electrophoresis (SDS-PAGE) analysis of seed storage protein showed genetic variations among fenugreek germplasms, both quantitatively and qualitatively, generating a total of 168 polypeptide bands with different molecular weights ranging from 4.5 to 300 kDa. Twenty-six of these bands were polymorphic, with a considerable polymorphism value (80.00%). Furthermore, restriction fragment length polymorphism (RFLP) analysis was also employed, which was based on the ability of four restriction enzymes (EagI, EcoRI, FspI, and HindIII) to cleave genomic DNA of the plant materials at specific target nucleotide sequences into different numbers of DNA fragments. RFLP analysis revealed 166 fragments with known sequences and variable lengths ranging from 80 to 4000 bp with a highly degree of polymorphism (88.71%). Data derived from SDS-PAGE or RFLP analyses were used to produce dendrograms, which clustered the studied fenugreek accessions into different groups based on the unweighted pair group method with arithmetic mean (UPGMA). The resulting relationships indicated that these two marker techniques were nearly equivalent, but not identical, with respect to phylogenetic information. In conclusion, SDS-PAGE analysis of seed proteins should be augmented with RFLP analysis of DNA for reliable estimates of genetic diversity among fenugreek germplasms.