Here's a very informative article by Ben Horowitz, about how to go about the complicated and painful task of firing an executive. Some key points:
While it's possible to fire an executive for bad behavior, incompetence or laziness, those cases are rare and relatively easy. Unfortunately, unless you have a horrible hiring process, those are probably not the reasons why you got to this point. At this level, almost every company screens for the proper skill set, motivation, and track record. Yes, the reason that you have to fire your head of marketing is not because they suck; it's because you suck.
(...)
But keep in mind that your choices are: a) alarm the board or b) enable an ineffective executive to remain in her position. While choice (a) is not great, it's a heck of a lot better than choice (b). Leaving a failing leader in place will cause an entire department in your company to slowly rot. Let that happen and the board will be more than alarmed.
Worth reading the whole article carefully, and hoping that you won't need the information inside too often.
