An untargeted shot-gun approach is described for the ultra-high-resolution analysis of fennel proteins by Fourier transform ion cyclotron resonance mass spectrometry (FT-ICR-MS) combined with a home-made Matlab search algorithm. The first step of the proposed bioinformatic strategy was the development of a custom-made fennel protein database, starting from the well-known, on-line available, protein NCBI database, under Foeniculum Vulgare organism, consisting of 231 total proteins. Partial and redundant forms of proteins, repeatedly included in the official NCBI database under different codes, were removed. In the final custom-made database, in addition to the 92 fennel specific non-redundant proteins, 10 proteins belonging to recognized allergenic sources associated with spice-mugwort-allergy syndrome (celery, carrot, parsley, birch, and mugwort) were also included. The second step was the in-silico enzymatic digestion, performed on all the 102 proteins, to obtain a theoretical list of m/z dataset of tryptic peptides. The Matlab processing data was the third and crucial step, necessary to search for in-silico mass calculated peptide sequences in the high resolution ICR mass spectra of the digested fennel extract. The final step was based on database searching in Peptide Mass Fingerprint (PMF) mode by using the matched m/z values as input data. The PMF search results confirmed the presence of 70 proteins (61 fennel specific and 9 allergenic proteins) inside the fennel extract.