Non-constructive existence proofs are critical in random graph theory, and that in turn is producing all sorts of useful results about what's possible, what's not possible, and what might be possible but it's likely to be hard.

A specific example, I'm working with some people on producing instances of G3C that may lead to a new form of PKC that is expected to be securely based on a known NPC problem. Non- constructive asymptotic existence proofs are critical to proving these instances are difficult.