I say:
Muhammad ibn Isḥāq, then al-Wāqidī, al-Bukhārī, and after them al-Bayhaqī, all record delegations whose arrival actually predates the ninth year—indeed, even predates the Conquest of Mecca itself.

The Almighty has said:
“Those of you who spent and fought before the Conquest are not equal to those who spent and fought afterwards; they are greater in rank than those who came later. Yet to each Allah has promised the finest reward.” (Qur’an 57:10)

We have already cited his ﷺ statement on the day of the Conquest (1): “There is no migration [after the Conquest], only striving and intention.” (2)

It is therefore necessary to distinguish between the early delegates whose coming occurred before the Conquest—so that their visit is deemed a hijrah—and those who arrived afterward, whom Allah has nevertheless promised goodness and the best reward, though they are not on a par with the former in precedence and merit. Allah knows best. Moreover, the eminent scholars who compiled the reports of these delegations have still left out certain matters.

By Allah’s praise and favor we shall relate what they transmitted, point out what needs pointing out, and add—if Allah wills—whatever has reached us of what they overlooked. In Him we place our trust and upon Him we rely.

Muhammad ibn ʿUmar al-Wāqidī (3) said: Kathīr ibn ʿAbd Allāh al-Muzanī related to us, from his father, from his grandfather, who said:
“The first people from Muḍar to come as a delegation to the Messenger of Allah ﷺ were four hundred men of Muzaynah. That was in Rajab of the fifth year. The Messenger of Allah ﷺ established the hijrah for them in their own homeland and said, ‘You are emigrants wherever you may be, so return to your property.’ They therefore went back to their land.”

Al-Wāqidī then related, on the authority of Hishām ibn al-Kalbī with his chain, that the first man to arrive from Muzaynah was Khuzāʿī ibn ʿAbd Nuhm (4), accompanied by ten of his tribesmen. He pledged allegiance to the Messenger of Allah ﷺ on behalf of his people’s Islam. When he returned to them, however, he did not find them as he had supposed; they held back. The Messenger of Allah ﷺ thereupon directed Ḥassān ibn Thābit to compose verses that alluded to Khuzāʿī without satirizing him directly, and he produced some lines (5). When those verses reached Khuzāʿī he complained to his people; they gathered around him, embraced Islam, and he brought them to the Messenger of Allah ﷺ. On the day of the Conquest the Messenger of Allah ﷺ handed the banner of Muzaynah—who numbered a thousand that day—to this same Khuzāʿī (6).

He further said: This Khuzāʿī was the brother of ʿAbd Allāh Dhū al-Bijādayn (7).