I guess the answer would depend on how important your boss is to your job. If you can't trust your boss but he's just some line manager in a ten-deep chain who doesn't really affect what you do on a day-to-day basis, maybe it doesn't impact you. On the other hand, maybe it's a sign of a toxic corporate culture, centered more around backstabbing and individual achievement than a whole-company team-based approach, and if you left tomorrow it wouldn't be soon enough. Like most metrics, the perceived truthfulness of one's boss really discards too much context to be useful, absent other data, for evaluating something like this.

Lying is endemic in corporate culture; success in corporations is not the same as being good at your job. Watch out for Snakes in suits.

I suggest creating or finding a work situation where the group isn't big enough for bosses, and thus corporate culture.

Get out of there quickly, for sure. I think nathanb's comment below should drive how quickly you leave, not if you leave.