By being unable to use his warchest on a changing market. As an example: missing the smartphone boat twice (once with Windows Mobile vs Symbian, and once with Windows Phone vs iOS/Android). Another example: Microsoft search / Bing.
Microsoft kept Office relevant though, made Azure relevant, and are reinventing themselves from a proprietary to a data company (like Google, Facebook, and Amazon) who also do a lot of open source (like the previously mentioned companies). But I suppose Nadella takes credit for that.
My guess is the algorithms and infrastructure serve search functions across all of their products. The "search market" is really the "Display advertising" market, and sure, they suck at that because no one goes to bing. But bing isn't worthless.
On the other hand there's not much evidence that MS could've won (or at least secured a place in) the smartphone wars with any other CEO. Many other big companies tried and failed miserably.
Microsoft kept Office relevant though, made Azure relevant, and are reinventing themselves from a proprietary to a data company (like Google, Facebook, and Amazon) who also do a lot of open source (like the previously mentioned companies). But I suppose Nadella takes credit for that.