As frustrating as it is,
@DND_Reborn already gave the best solution in my opinion:
Dungeons & Dragons is a game. And like many other games, it has multiple "win" conditions and multiple "lose" conditions. You don't play poker assuming you can win every hand. You don't play chess with the expectation of always beating your opponent. You don't go bowling and expect to fill your score card with strikes every single night. No football team is always undefeated forever. Etc.
So the only thing I would add (and I see that others have added it as well) is that "killing them" is just one Lose Condition. They could be captured, turned into werewolves, robbed and left for dead, rescued by an insufferable thunder-stealing NPC superhero who takes all the credit, etc. I'd start out with smaller, less-severe consequences and then gradually make them more painful over time, so that they understand that (1) failure is always possible, (2) it's often unpleasant, (3) it's unpredictable, (4) failure isn't a punishment, and (5) the game will go on even after defeat/failure.
This one last one might be my own baggage: the players need to understand that you aren't going to be "reshuffling the deck," and they aren't going to "teach the DM a lesson" by doubling down. Believe it or not, there are players out there who will effectively hold the group hostage with the threat of game night cancellations or even a campaign-ending TPK in order to get what they want. I've only had to deal with that kind of stubborn "play my way or I'll take my ball and go home" mentality once, and I ended up losing two players over it.