First the background. The great Jewish philosopher and poet of the Middle Ages, Spanish-born Yehudah Ha-levi (1075-1141) was a great lover of Zion. It was he who wrote the moving words that stirred the hearts of countless for a thousand years: "My heart is in the east, and I in the uttermost west..." --
...ליבי במזרח ואנכי בסוף המערב
Eventually, according to legend (and documentary evidence from the Cairo Geniza) he did travel to the land of his heart and dreams, the land of Israel. In a legend, first recorded in Gedalyah ibn Yahya's 16th century historical chronicle שלשלת הקבלה, a tragedy occurred after arriving in the Holy Land:
וקבלתי מזקן אחד שבהגיעו אל שערי ירושלים קרע את בגדיו והלך בקרסוליו על הארץ לקיים מה שנאמר כי רצו עבדיך את אבניה ואת עפרה יחוננו והיה אומר הקינה שהוא חבר האומרת ציון הלא תשאלי וכו' וישמעאל אחד לבש קנאה עליו מרוב דבקותו והלך עליו בסוסו וירמסהו וימיתהו
"I heard from an old man that when he reached the gates of Jerusalem he tore his garment [as a symbol of mourning the destruction of Jerusalem] and knelt on the earth to fulfill the verse ' For Thy servants take pleasure in her stones, and love her dust,' [Psalm 102.15] and he recited the elegy which he had written, 'Zion, will you not inquire . . . ?'. [And at that moment] an Arab [Muslim] rider [who has witnessed the sight] grew jealous of his ecstatic state and trampled upon him with his horse and he died."
(Pg. 92 in the edition I linked to.)
However, as Eliezer Brodt wrote (in an excellent, thorough post at the Seforim Blog) this legend was doubted in the 19th century, chiefly because at the time of Yehudah Ha-levi Jerusalem was ruled by Crusaders, and so it seemed impossible that such a lawless action, that of a haughty noble, could be taken by a Muslim in Jerusalem at that time.
"R. Matisyahu Strashun . . . questions the legend. He explains that Jerusalem, in the times of R. Yehuda Halevi, was ruled by Christians and not by Arabs. R. Strashun allows that although it is possible R. Yehuda Halevi composed Zion Halo Tishali when he got to Jerusalem -- not that we know that he did -- but the part of the story with the Arab killing him is certainly not true . . . R. Shmuel David (ShaDaL) Luzzatto in his collection of poems from R. Yehuda Halevi, Besulas Bas Yehuda (Prague, 1840), also questions the the legend due to the Christian and not Arab control during the time of R. Yehuda Halevi. Further, even if there were Arabs around they would not have done such a blatant act right at the city gate (pp. 25-26). So Shadal concludes that he died on his way from Egypt never even reaching Eretz Yisroel. . . ."
Indeed, at that moment in time Muslims were in the same boat as Jews in Jerusalem; that is, downcast. Furthermore, there wasn't even any evidence that Yehudah Ha-levi had ever even reached Israel. A happening first reported 400 years after the fact, without evidence and a major question about the plausibility of it (coupled with the fact of Muslim rule in Jerusalem at the time of the story's reporting) certainly suggests that the story be classified as legendary. (Even without this doubt, one can discern that this story is almost O. Henry-like, that is, it seems like a great story, just not what probably happened in real life." It has since been established that he did reach the Holy Land, but the circumstances of his death are not known. Most recountings responsibly note that it is a legend.1
I came across A Brief History of the Jewish People by Moshe Weiss (Rowman & Littlefield, 2004) and read the following:
As you can see, this retelling does not report it as fact, but as a legend. However, presumably being aware of the objection that the story could not have occurred as reported, the author takes the liberty of conjecturing that it was a Christian, not Arab [Muslim] horseman. Indeed, that could have been the case--but the only source for the story specifically says that it was a Muslim!
An interesting synthesis. I am not suggesting that Weiss meant to suggest that the story occurred as a historical fact, but for some reason he seems to have felt that it was a good idea to at least make the legend plausible!
As an aside, searching on Google Books one sees many retellings of this story. In some he is trampled by the horse (as written) and in a few he is speared by the rider. I am not sure where the spear or lance came from, but it is interesting how some imagine details that are not in texts which they are retelling.
1 Including Artscroll's edition of Tisha B'av kinnot.