Change hostname displayed on shell tty

While installing my system I've chosen a wrong hostname because I thought it would be easy to change later on but I've been looking for a proper way to fully change it for a while now but the only things I've found were editing /etc/hostname and using the hostname command.

Both of these don't seem to quite work for me...
For example when I open a command line tty it still prompts me with

<old-hostname> login:

even though I fully expected it to prompt me with

<new-hostname> login:

Additionally in the local network my computer is still identified with the old hostname...
Are there any other files that could contain an instance of the hostname?