It was narrated from Ibn 'Abbas (رضي الله عنه) that

The Messenger of Allah (ﷺ) said: "The Black Stone is from Paradise. It was whiter than snow until the sins of the people of shirk turned it black.”