Yes, a VPN can work over a satellite Internet connection. However, keep in mind that your traffic will be encrypted and have to pass through a VPN server first. This will inevitably cause slowdowns, especially if your ISP isn’t the fastest to begin with.