كتاب الإيمان
1
The Book of Faith
(54)
Chapter: Islam destroys that which came before it, as do Hijrah (Emigration) and Hajj
(54)
باب كَوْنِ الإِسْلاَمِ يَهْدِمُ مَا قَبْلَهُ وَكَذَا الْهِجْرَةُ وَالْحَجُّ ‏‏
Sahih Muslim 122

It is narrated on the authority of Ibn 'Abbas that some persons amongst the polytheist had committed a large number of murders and had excessively indulged in fornication. Then they came to Muhammad (ﷺ) and said:

Whatever you assert and whatever you call to is indeed good. But if you inform us that there is atonement of our past deeds (then we would embrace Islam). Then it was revealed: And those who call not unto another god along with Allah and slay not any soul which Allah has forbidden except in the cause of justice, nor commit fornication; and he who does this shall meet the requital of sin. Multiplied for him shall be the torment on the Day of Resurrection, and he shall therein abide disgraced, except him who repents a believes and does good deeds. Then these! for the Allah shall change their vices into virtues. Verily Allah is Ever Forgiving, Merciful (xxv. 68-70). Say thou: O my bondsmen woo have committed extravagance against themselves despair not of the Mercy of Allah I Verily Allah will forgive the sins altogether. He is indeed the Forgiving, the Merciful (xxxix. 53).
حَدَّثَنِي مُحَمَّدُ بْنُ حَاتِمِ بْنِ مَيْمُونٍ، وَإِبْرَاهِيمُ بْنُ دِينَارٍ، - وَاللَّفْظُ لإِبْرَاهِيمَ - قَالاَ حَدَّثَنَا حَجَّاجٌ، - وَهُوَ ابْنُ مُحَمَّدٍ - عَنِ ابْنِ جُرَيْجٍ، قَالَ أَخْبَرَنِي يَعْلَى بْنُ مُسْلِمٍ، أَنَّهُ سَمِعَ سَعِيدَ بْنَ جُبَيْرٍ، يُحَدِّثُ عَنِ ابْنِ عَبَّاسٍ، أَنَّ نَاسًا، مِنْ أَهْلِ الشِّرْكِ قَتَلُوا فَأَكْثَرُوا وَزَنَوْا فَأَكْثَرُوا ثُمَّ أَتَوْا مُحَمَّدًا صلى الله عليه وسلم فَقَالُوا إِنَّ الَّذِي تَقُولُ وَتَدْعُو لَحَسَنٌ وَلَوْ تُخْبِرُنَا أَنَّ لِمَا عَمِلْنَا كَفَّارَةً فَنَزَلَ ‏{‏ وَالَّذِينَ لاَ يَدْعُونَ مَعَ اللَّهِ إِلَهًا آخَرَ وَلاَ يَقْتُلُونَ النَّفْسَ الَّتِي حَرَّمَ اللَّهُ إِلاَّ بِالْحَقِّ وَلاَ يَزْنُونَ وَمَنْ يَفْعَلْ ذَلِكَ يَلْقَ أَثَامًا‏}‏ وَنَزَلَ ‏{‏ يَا عِبَادِيَ الَّذِينَ أَسْرَفُوا عَلَى أَنْفُسِهِمْ لاَ تَقْنَطُوا مِنْ رَحْمَةِ اللَّهِ‏{‏ ‏.‏
Reference : Sahih Muslim 122
In-book reference : Book 1, Hadith 229
USC-MSA web (English) reference : Book 1, Hadith 221
  (deprecated numbering scheme)