It doesn't have to. You can rent a physical server from one of the many companies out there.
You get a few IP addresses (I've got a /29 on both of my servers) and a fresh install of whatever distro you choose with sshd running. It's just like purchasing a VPS.
They're the exact same thing except one is running inside virtualization software and the other is running on a real CPU.