منشأ این شهرت آن بوده که در سال ۲۰، در زمان لشکرکشی سپاهیان اسلام برای فتحمصر، عمروبن عاص از عمر تقاضای کمک کرد. عمر نیز لشکری چهار هزار نفری به یاری او فرستاد و به وی نوشت که فرمانده هر هزار نفرِ این لشکر، مردی است که خود به جای هزار نفر است، و از جمله آن فرماندهان خارجة بن حذافة بود
پس از آنکه عمروبن عاص فسطاط را فتح کرد، خارجة بن حذافة از طرف وی به شهرهای فَیّوم و اُشمونَین و اِخمیم و بَشَرودات و روستاهای ناحیه صعید لشکر کشید و بر آنها چیره شد.
در سال ۴۰، در ماجرای توطئۀ خوارج برای قتلعلی علیه‌السلام و معاویه و عمروبن عاص، خارجة بن حذافة به اشتباه به جای عمروبن عاص کشته شد، زیرا از قضا عمروبن عاص در شب قبل از این حادثه به دل‌درد سختی مبتلا شد و هنگام صبح به خارجة بن حذافة دستور داد با مردم نماز بگزارد. مردی از خوارج صیداوی خارجة بن حذافة را عمروبن عاص پنداشت و او را کشت.
قاتل خارجة بن حذافة وقتی دستگیر و با عمروعاص روبه‌رو شد و فهمید که خارجة بن حذافة کشته است، گفت «اَرَدْتُ عَمرآ و اَرادَاللّهُ خارجةَ» و این گفتۀ وی ضرب‌المثل شد.
