How can HSTS prevent a man in the middle attack if the server has not even been contacted yet?

It can't, that is what preloading is for. Your browsers comes preloaded with a list of all sites that have requested HSTS preload, so your browser will use HTTPS even on the first visit. This is why preloading on all subdomains is potentially dangerous to use, it could break your site if you don't have HTTPS everywhere.

But even without preloading HSTS will improve security. Yes, the first visit will be susceptible to MITM, but every visit after that is not. This makes it a lot more difficult for an attacker as they must intercept the very first visit for the attack to work.

HSTS preload list is compiled into browser binary: https://chromium.googlesource.com/chromium/src/net/+/master/... https://dxr.mozilla.org/mozilla-central/source/security/mana...

It can only do that if you add it to the preload lists of browsers (which is mentioned in the article).

But even if it is not, it's still helpful for people connecting to your site again.

And because the preload list is hierarchical whole swathes of the Web can be covered with a single entry. .dev is the biggest example, but they can protect all the stack exchanges, all the default blogspot blogs, that sort of thing.

It can't! But after the first time it's been contacted, when you contact it again HSTS will enforce HTTPS (from the client itself - much stronger than a redirect).