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