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