SSH connection not possible: "Host key verification failed"

I was not able to connect to my ssh server. I tried to log in for the first time, but I always received the above mentioned error:

The authenticity of host '...' can't be established.
ECDSA key fingerprint is SHA256:.... Are you sure you want to continue connecting (yes/no/[fingerprint])?
Host key verification failed.

The problem: a known_host file is not existing, because this was my first time connecting.

I could finally resolve this by forcing ssh to not verify the host key with the following command:

ssh -o StrictHostKeyChecking=No user@adress

Then, also the known_host file was generated.

Anyway, I would like to know why it was not possible to connect before that. Normally it should work, shouldn't it? And is it a safety risk to solve this issue like that? As I understood, ssh will never verify the host key now for this specific connection.

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.