Yemenite Jews have a unique religious tradition that marks them out as separate from Ashkenazi, Sephardi, and other Jewish groups. Yemenite Jews are generally described as belonging to "Mizrahi Jews", though they differ from the general trend of Mizrahi groups in Israel, which have undergone a process of total or partial assimilation to Sephardic culture and Sephardic liturgy. (While the Shami sub-group of Yemenite Jews did adopt a Sephardic-influenced rite, this was in no small part due to it essentially being forced upon them, and did not reflect a demographic or cultural shift).
Some Jewish families have preserved traditions relating to their tribal affiliation, based on partial genealogical records passed down generation after generation. In Yemen, for example, some Jews trace their lineage to Judah, others to Benjamin, while yet others to Levi and Reuben. Of particular interest is one distinguished Jewish family of Yemen who traced their lineage to Bani, one of the sons of Peretz, the son of Judah.
There are numerous accounts and traditions concerning the arrival of Jews in various regions in Southern Arabia. One tradition suggests that King Solomon sent Jewish merchant marines to Yemen to prospect for gold and silver with which to adorn his Temple in Jerusalem. In 1881, the French vice consulate in Yemen wrote to the leaders of the Alliance (the Alliance Israelite Universelle) in France, that he read in a book by the Arab historian Abu-Alfada that the Jews of Yemen settled in the area in 1451 BC. Another legend says that Yemeni tribes converted to Judaism after the Queen of Sheba's visit to king Solomon. The Sanaite Jews have a tradition that their ancestors settled in Yemen forty-two years before the destruction of the First Temple. It is said that under the prophet Jeremiah some 75,000 Jews, including priests and Levites, traveled to Yemen. Another legend states that when Ezra commanded the Jews to return to Jerusalem they disobeyed, whereupon he pronounced a ban upon them. According to this legend, as a punishment for this hasty action, Ezra was denied burial in Israel. As a result of this local tradition, which can not be validated historically, it is said that no Jew of Yemen gives the name of Ezra to a child, although all other Biblical appellatives are used. The Yemenite Jews claim that Ezra cursed them to be a poor people for not heeding his call. This seems to have come true in the eyes of some Yemenites, as Yemen is extremely poor. However, some Yemenite sages in Israel today emphatically reject this story as myth, if not outright blasphemy.
Archaeological records referring to Judaism in Yemen started to appear during the rule of the Himyarite Kingdom, established in Yemen in 110 BC. Various inscription in Musnad script in the second century CE refer to constructions of synagogues approved by Himyarite Kings. According to local legends, the kingdom's aristocracy converted to Judaism in the 6th century CE. The Christian missionary, Theophilos, who came to Yemen in the mid-fourth century, complained that he had found great numbers of Jews. By 380 A.D, Himyarites religious practices had undergone fundamental changes. The inscriptions were no longer addressed to El Maqah or 'Athtar, but to a single deity called Rahman. Debate among scholars continues as to whether the Himyarite monotheism was influenced by Judaism or Christianity. Jews became especially numerous and powerful in the southern part of Arabia, a rich and fertile land of incense and spices and a way station on the routes to Africa, India, and East Asia. The Yemeni tribes did not oppose Jewish presence in their country. By 516, tribal unrest broke out, and several tribal elites fought for power. One of those elites was Joseph Dhu Nuwas or "Yûsuf 'As'ar Yaṯ'ar" as mentioned in ancient south Arabian inscriptions. The actual story of Joseph is murky. Greek and Ethiopian accounts, portray him as a Jewish zealot. Some scholars suggest that he was a converted Jew. Nestorian accounts claim that his mother was a Jew taken captive from Nisibis and bought by a king in Yemen, whose ancestors had formerly converted to Judaism. Syriac and Byzantine sources maintain that Yûsuf ’As’ar sought to convert other Yemeni Christians, but they refused to renounce Christianity. The actual picture, however, remains unclear.
Some scholars believe that Syriac sources reflected a great deal of hatred toward Jews. In 2009 a BBC broadcast defended a claim that Yûsuf ’As’ar offered villagers the choice between conversion to Judaism or death and then massacred 20,000 Christians. The program's producers stated that, "The production team spoke to many historians over 18 months, among them Nigel Groom, who was our consultant, and Professor Abdul Rahman Al-Ansary ." Inscriptions attributed to Yûsuf ’As’ar himself show the great pride he expressed after killing more than 22,000 Christians in Ẓafār and Najran. According to Jamme, Sabaean inscriptions reveal that the combined war booty (excluding deaths) from campaigns waged against the Abyssinians in Ẓafār, the fighters in ’Ašʻarān, Rakbān, Farasān, Muḥwān (Mocha), and the fighters and military units in Najran, amounted to 12,500 war trophies, 11,000 captives and 290,000 camels and bovines and sheep.
Historian Glen Bowersock described this as a "savage pogrom that the Jewish king of the Arabs launched against the Christians in the city of Najran. The king himself reported in excruciating detail to his Arab and Persian allies about the massacres he had inflicted on all Christians who refused to convert to Judaism." There were also reports of massacres and destruction of places of worship by Christians too. Francis Edward Peters wrote that while there is no doubt that this was a religious persecution, it is equally clear that a political struggle was going on as well. It is likely that Dhu Nuwas was a leader of a liberation movement seeking to free Yemen from an increasing foreign meddling in the nation's affairs, and Judaism became a vital element in the resistance.
According to ‘Irfan Shahid’s Martyrs of Najran – New Documents, Dhu-Nuwas sent an army of some 120,000 soldiers to lay siege to the city of Najran, which siege lasted for six months, and the city taken and burnt on the 15th day of the seventh month (i.e. the lunar month Tishri). The city had revolted against the king and they refused to deliver it up unto the king. About three-hundred of the city’s inhabitants surrendered to the king’s forces, under the assurances of an oath that no harm would come to them, and these were later bound, while those remaining in the city were burnt alive within their church. The death toll in this account is said to have reached about two-thousand. However, in the Sabaean inscriptions describing these events, it is reported that by the month Dhu-Madra'an (between July and September) there were “1000 killed, 1500 prisoners and 10,000 head of cattle.”