I have fired someone who, if you asked him, would probably tell you that he was fired for no reason. This was a very personable, hard working, smart guy I was hoping would be a developer. He was hired to fill two roles 50-50: one he was objectively bad at and the other he was abysmally awful at. His self assessment on both these roles was that the first was "flawless" and the second "is getting there but I know it needs some work." He told me that he never made the same mistake twice, but he did, all the time - he just didn't realize it was the same mistake.
For example, being given some tentative requirements for making an estimate, then hearing in a meeting that the project looked like it was was going to go ahead, and immediately getting started using those requirements, without waiting to hear that the project had been sold or confirming the final requirements. On being told it was sold, not looking in the location we keep requirements to see it had been updated, and not asking the person who said "do it now" whether anything had changed. The second time he did this, he said it wasn't the same mistake because one was a Windows application and one was a web site. I have many more examples which I will spare you.
Eventually he was on the tightest leash imaginable: having to send detailed steps of what he planned to do each day, and loop back to tell us how he did against the plan. He never met the plan but he always had a reason and didn't see the pattern. Things would take twice as long as planned, or 4 times, or even ten times! I remember a task my other developer felt would take 2 hours that was taken away from this guy after a week, although as he pointed out, he didn't spend 40 hours on it, probably only 20. The other developer finished it in an hour. There was more than one meeting in my office with the door closed where I said "this can't go on, this cannot keep happening." He was not on any billable projects, only internal-use ones, because it was impossible to keep promises to clients if tasks were given to him.
And when he asked me, while I was away visiting a dying relative, if we could meet when I got back to talk about what he needed to do to get the raise he felt he was owed because he had been with us a year and his wife was really pushing him to earn more money, I decided he would never realize how far his performance was from where it needed to be, and I fired him. He was utterly blindsided and furious. But he was not fired "for no reason." Should this happen to you, you can say it must have been personal, somebody must have been jealous, or whatever else you like but the chances are you were so bad at that job you didn't even realize you were bad.
It might then be useful to look back over meetings and emails and try to look at them with new eyes: "what if all this is about my not being very good at this work?" Yes, there is praise in this email and this review, but now that I look closely, there is also some criticism. Hmmm..." You may learn something important about yourself.
What do you say in the interview? One of my other former staff members suggested this employee apply to a specific job (at that employee's new employer) that needed something he was very good at, and had no need for the skills he was so abysmal at. He applied there and told them (truthfully) that our work mix and business model were not a good fit for him, which is why he was applying to something so different. He got the job and was a bit of a star there, promoted repeatedly to the extent the recommender was thought more highly of for bringing him to them.
So a happy ending for everyone because he was doing something he was good at. I don't know if he told them he was fired or he quit, and I don't care. I only kept him around as long as I did because I liked him, and I was genuinely happy that he found something he was good at. But I bet if you asked him he'd say I blindsided him, fired him for no reason, and did it out of personal dislike or some other "politics" reason.