Yes, PDAs had already been a thing for a long time (Psion Organizer), and Apple themselves had experimented with this category too with the Newton, before the Palm Pilot then became so dominant.

What was novel about the smart phone - really it's defining characteristic, was it wasn't a primarily single purpose device like a PDA, or phone, or MP-3 player/iPod, or camera, or handheld web browser, but rather a universal hand held computer/communications device, and one whose functionality was not limited to what you got out of the box. The large touch screen, with gesture-based UI, was also quite novel, and a large part of what made it successful and generic.

It's easy to look in the rear view mirror and say that most inventions/innovations were inevitable and just a product of their times, but the iPhone was quite shocking when first launched and did shake up the industry - nobody was expecting it, or expecting how popular such a device would be. Steve Ballmer famously laughed at the iPhone after it's launch and questioned who would want it, given the high cost and lack of a keyboard (a feature, not a deficit!).. and then of course went on to try unsuccessfully to copy it.