An apparatus and method for providing a virtual private network (VPN) service based on mutual authentication are provided, the apparatus including a storage unit configured to store a first public key and a second public key; an authentication unit configured to authenticate a VPN server with the first public key and to authenticate a user device with the second public key; and a tunnel management unit configured to generate a first VPN tunnel and a second VPN tunnel to relay data between the user device and the VPN server based on the authentication of the VPN server and the user device by the authentication unit.