Unless you can prove (e.g. using your old device or a recovered signing key) that the new device is yours. In that case, if the service supports it, the new dev

Unless you can prove (e.g. using your old device or a recovered signing key) that the new device is yours. In that case, if the service supports it, the new device could automatically ask your contacts to re-send the old messages using the new device's public key.