أمر النبي صلى الله عليه وسلم المسلمين بالهجرة إلى المدينة قاعدة المسلمين الأمينة، فهاجر حمزة مع من هاجر إلى المدينة المنورة قبيل هجرة النبي صلى الله عليه وسلم إليها بوقت قصير، فنزل حمزة وزيد بن حارثة وأبو مرثد كناز بن حصن، ويقال: ابن حصين، وابنه مرثد الغنويان حليفا حمزة علي كلثوم بن هدم، أخي بني عمرو بن عوف بـ (قباء) ، ويقال: بل نزلوا على سعد بن خيثمة، ويقال: نزل حمزة على أسعد بن زرارة أخي بني النجار.