(Historical note: This answer was written before the question was edited to ask for "the first". I'm not changing it because I think it's more informative the way it is.)
Yes, it has happened, though it's rare. The trick seems to be how strong of a replacement character they can get to fill the void, and how well the show's supporting cast is at holding it together in the mean time.
A good example of a success would be Cheers. Though it was technically an ensemble show, for all intents and purposes, the stars of Cheers were Ted Danson and Shelley Long. Long left in the fifth season and was replaced by Kirstie Alley and the show would continue to be successful for another six seasons. This is largely due to the fact that Danson and Alley also developed a good on-screen chemistry, while the rest of the cast was strong enough to keep the show around while that happened.
Two And A Half Men is another example, though one could argue that losing Charlie Sheen and replacing him with Ashton Kutcher doesn't count as "successfully continuing"; the show did OK for the first two seasons post-Sheen but plummeted in the ratings after that. Again, the presence of Angus T. Jones is likely what help keep the show around (after he left, the show did tank in the ratings and get cancelled).
There is also a fairly large list of cases where a show loses it's lead actor, but the character s/he plays remains on the show. This is less common in modern TV than is used to be, and usually happens to bit parts or recurring characters, but it has been done with lead roles. The two "trope namers" (which may not be the earliest examples, but are by far the most well-known) are Bewitched, which swapped out Dick York for Dick Sargent in the lead role of Darrin, and Doctor Who, which made replacement of the actor playing The Doctor a key plot element from very early in the show's run.
(Historically speaking, by the way, this does not bode well for Castle, but may mean Sleepy Hollow has a chance. Of course, both are doing terrible with both co-leads, so it may be irrelevant.)