A relay device communicates with a server and a client device and includes a storage and a controller. The controller is configured to: receive, from the server, service use information which is to be used for the client device to use a service; transmit the received service use information to the client device; receive, from the client device, transmission instructing information containing key information which identifies CA certificate data stored in the storage and used for the client device to verify server certificate data; and transmit, to the client device, the CA certificate data identified by the key information contained in the received transmission instructing information. The CA certificate data is stored in the storage.