An authentication information issuing apparatus is configured to issue authentication information with which a vehicle is unlocked, to a portable terminal, the vehicle being capable of containing a parcel and being locked and unlocked based on the authentication information acquired from the portable terminal, and includes a storage device, an acquiring device and an authentication information sending device. The storage device is configured to store a parcel receipt ID as information with which a delivery destination of the parcel is specified and a vehicle ID as information with which the vehicle is identified, in association with each other. The acquiring device is configured to acquire the parcel receipt ID associated with a target parcel. The authentication information sending device is configured to send the authentication information with which a vehicle as a containment destination of the parcel is unlocked, to the portable terminal, based on the acquired parcel receipt ID.