I think you're referring to the story of R. Elazar ben Dodaya, which can be found in Avodah Zarah 17a.
To summarize the story, it was said about a man named Elazar ben Dodaya that there was not a prostitute in the world that he had not been with. When he heard of a distant beautiful woman, he went to go be with her. In the middle of his act, the woman told him that there was no way for him to repent for his wrongdoings. This disturbed Elazar ben Dodaya greatly, and he went out and did complete repentance for his misdeeds. He did so much teshuvah that eventually his soul left him. A Heavenly voice then announced, "Rabbi Elazar ben Dodaya is destined for the World to Come." When R. Yehudah HaNasi heard this story, he cried and said, "There are those (like me) who receive a share in the World to Come after many years, and those who receive it in an instant."