I believe that Chinese characters are born with radicals, but they were not classified by radicals until Shuowen Jiezi.
To understand why radicals appeared at that time, we need to know that in the Warring States period (about 475-221 BC), characters between states could be quite different. The First Emperor of Qin (Ying Zheng, known as Qin Shihuang) unified the writing form of Chinese, and ordered his chancellors to invent Lishu, a typeface that can still be seen today. Shuowen Jiezi was published in Eastern Han Dynasty, when the shape of most Chinese characters had not been changed for centuries. Therefore, only then could a dictionary with radical index be possible.
It could also be possible that the author of Shuowen Jiezi created a radical index for people to look up characters with similar meanings in the dictionary, as a radical may indicate a certain type of meaning. For example, people who want to express a concept related to water may look up for radical "水"(shui).