Is it true that radicals were introduced for this purpose, long after many characters already existed?
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).
I think your phrasing may be ambiguous, so I'll answer in two ways. If you're asking if characters didn't have a radical and then one was added - thereby changing the character - for classification purpose, then of course the answer is no.
If the question is to know whether the "concept" of radical existed, then you can think of it this way: if people had a concept of radical in their mind prior to the Shuowen, then it had to be a way for them to classify those characters. Indeed, the people who could write did see the parts of a character, but a "radical" is a component that's considered more important/interesting: apart from classification, what role could it serve?
Therefore, the concept of radicals has to come with a desire to classify characters... of which the Shuowen is the first known example.