وسار حارثة بن ثعلبة بابني الأوس والخزرج إلى يثرب، فأدركه أبوه ثعلبة قريب مكة، فلما مروا بمكة وبها جرهم، قاتلهم جرهم، فمضوا إلى الجحفة، وسار ثعلبة إلى الشام فمات، وقام من بعده ابنه حارثة بن ثعلبة، فنزل الشام وبها سليخ من قبل الروم، فنزلوا معهم حتى أتاهم جابي قيصر ملك الروم لأخذ الإتاوة، فأنف حارثة وقومه من ذلك، وجرت لهم [مع الروم] خطوب، آخرها أن سار حارثة وولده الأوس والخزرج و [بنو] أبيه إلى يثرب، وأقام بنو ضعيف بن عمرو بن عامر وأخوهم بالشام مع سليخ.
وكان بيثرب يومئذ اليهود، وملكهم شريف بن كعب، فكتب بينه وبين حارثة بن ثعلبة كتاب عهد، أقاموا زمانا في هدوء، ثم وقع الشر بينهم واقتتلوا فقتل من اليهود عددا كبير، وملكت العرب المدينة بما فيها، فاجتمع يهود تيماء، وخبير، وفدك، والعوالي على حربهم، فآل أمرهم إلى الصلح.
ونزل الأوس والخزرج بيثرب، وعمروها بجموعهم، فمات الملك حارثة ثم ثعلبة العنقاء، وقام من بعده ابنه العجلاء بن حارثة، وثارت يهود والأوس والخزرج، فقتلوا، وسلبوا، ونهبوا، فبعثوا إلى جبلة بن عمرو بن جبلة، ملك غسان يستصرخه، فأقبل من الشام لنصرتهم على اليهود، وحاربهم فقتل ملكهم شريف بن كعب في جمع كبير منهم، حتى ذلوا له، ثم عاد إلى الشام، فمات في طريقه.
وقام من بعده ابنه الحارث بن الجبلة، فسار إليه مالك بن العجلان ليهنئه بالملك، ففقد ليلا في بني قريظة، وقد عرش بمنازلهم، فأوقع بهم العجلان، وقتل منهم بضعا وثمانون رجلا بحيل دبرها، وكان قد قام بأمر اليهود بعد ملكهم شريف بن كعب، ابنه القيطون بن شريف - واسمه جوني، والقيطون لقب - فجمع يهود الحجاز، وتيماء، وفدك، والعوالي، وزحف إلى يثرب، فكان بينه وبين الأوس والخزرج قتال شديد، قتل فيه كثير من الفريقين فبعث العجلان يستنصر بطيئ وهم بأطراف نجد، فأتوه، وهزموا اليهود، وقتل القيطون في عدد كبير من قومه.