The PDA market was mostly created by the Newton in the early 90's. It had even built up a thriving ecosystem up until Saint Jobs second coming got it killed overnight (his revenge against Sculley). But even by then, Palm had already entered the market and for years they were the leaders on the PDA business. MS was the ugly duckling there, mostly starting with their Handheld PCs (remember those?) then switched to the PocketPC format to compete with Palm. They had limited success with those, but the main problem was that MS just stuck the "Windows Experience" upon a PDA instead of doing something different. Hell, even Symbian was king during the early smartphone years, and that one's basically rebadged EPOC (we miss you Psion!).
Then there's the thing that MS loves to deprecate their stuff. Look, we have Windows CE! Oh no, now it's Windows Mobile! Oh no, scratch that, Windows Phone 7 is totally new and anything from WinMo won't work here! Eventually the developer base evaporated and went to platforms that didn't do the deprecation dance every 2 years. Oh yes… and MS is responsible for the death of the one platform that did survive the PDA to Smartphone transition: Symbian. :(