Are radicals a relatively new invention for looking up dictionaries? According to this article, radicals were invented for looking up characters in a dictionary, and didn't exist until after the publication of the Shuōwén Jiězì [說文解字] (around 100 AD).

Is it true that radicals were introduced for this purpose, long after many characters already existed?
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.