Asparagopsis taxiformis (Delile) is a red marine macroalga (Rhodophyta) with high invasive potential and broad worldwide distribution. In the Mediterranean Sea, A. taxiformis was reported before the opening of the Suez Canal and is comprised of two different cryptic lineages, named L2 and L3. As for the Israeli Mediterranean Sea (IMS), A. taxiformis benthic populations have seemingly expanded with several large seasonal blooms recorded in recent years. However, neither ecology nor molecular substantial studies have been conducted for this particular geographical area. In this study, randomly samples specimens of A. taxiformis and preserved herbarium samples collected from the IMS in the past, were all barcoded and taxonomically identified using three molecular genetic markers (LSU, cox2-3 spacer, and rbcL). We found a cryptic lineage 4 (L4) of A. taxiformis first reported here for the Mediterranean Sea, and previously described for the western Indo-Pacific and Hawaii. Herbarium samples confirmed the presence of L4 as early as 2013. Comparative assessment of cox2-3 spacer marker indicates 100% similarity to sequenced L4 samples from Egypt in the Red Sea. The IMS cox2-3 spacer sequences differed from previously sequenced samples from the Mediterranean Sea by 2.3% and 3.9% bp, compared to L3 and L2 Mediterranean populations, respectively. Altogether, our results strongly indicate a Lessepsian migration route for A. taxiformis L4 with yet unknown consequences for the local marine ecosystems.