Mustadrak al-Hakim — Hadith 222

It is narrated from Sayyiduna Awf bin Malik al-Ashja'i (may Allah be pleased with him) that he said: We stopped at a halting place with the Messenger of Allah (peace and blessings be upon him). I woke up during the night and could not see anything taller than the back of my saddle (that is, everything was sunk in darkness); every person and camel was sleeping pressed to the ground. I made my way through the people until I reached the bed of the Messenger of Allah (peace and blessings be upon him), but he (peace and blessings be upon him) was not there. I placed my hand on the bed and it was cold (that is, time had passed since he had left). I passed among the people reciting 'Inna lillahi wa inna ilayhi raji'un' (We belong to Allah and to Him we return), fearing that the Messenger of Allah (peace and blessings be upon him) might have been taken away (by the enemy). Eventually I went out beyond the whole army, and there I saw a dark shape (a shadow). I threw a stone towards it and went towards it, and there were Sayyiduna Mu'adh bin Jabal and Sayyiduna Abu Ubaydah bin al-Jarrah (may Allah be pleased with them both). In front of us came a sound like the sound of a millstone turning, or like the sound of wind passing through a thicket of reeds. We said to one another: O people! Stay firm right here until morning comes or the Messenger of Allah (peace and blessings be upon him) comes to you himself. We stayed there for as long as Allah willed, then a voice called: "Are Mu'adh bin Jabal, Abu Ubaydah and Awf bin Malik there?" We said: Yes. He (peace and blessings be upon him) came to us. We did not ask him anything, nor did he tell us anything, until he sat down on his bed. Then he (peace and blessings be upon him) said: "Do you know what choice my Lord gave me tonight?" We said: Allah and His Messenger know best. He (peace and blessings be upon him) said: "Allah gave me the choice between half of my Ummah being admitted into Paradise and my being given the right of intercession, and I chose intercession." We said: O Messenger of Allah! Pray to Allah to make us among those who receive intercession. He (peace and blessings be upon him) said: "This intercession is for every (monotheist) Muslim."
This hadith is sahih (authentic) on the condition of Muslim, because he used Sulaym bin Amir as evidence, and (the two Shaykhs) agree on all its other narrators, but they did not record it.