It was kind of tricky to figure out, but it turned out that Heroku Postgre requires some SSL tricks to connect from outside. Here are my PHPStorm connection settings, Advanced tab:
Here’s a link to a blog post I wrote on Unknown Worlds blog. If you’re working in a highly-distributed team or you’re in gamedev, this one might be for you!