Remote attestation has emerged as a valuable security mechanism which aims to verify remotely whether or not a potentially untrusted device has been compromised. The protocols of Remote attestation are particularly important for securing Internet of Things (IoT) systems which, due to the large number of interconnected devices and limited security protections, are susceptible to a wide variety of cyber attacks. To guarantee the integrity of a software running on a single device, remote attestation is usually executed as an uninterrupted procedure: at the attestation time, a device stops the normal operation and executes the attestation of the entire device without interruption. The remote attestation protocols that aim to attest a large number of devices also follow the assumption on uninterrupted execution: when a device attests its network neighbours, each device verified in the neighborhood suspends its normal operation until the attestation protocol is completed. To avoid unnecessary suspension of the normal operation of the devices, this paper proposes a novel Secure Asynchronous Remote Attestation (SARA) protocol that releases the constraint of synchronous interaction among devices. In particular, SARA is an attestation protocol that exploits asynchronous communication capabilities among IoT devices in order to attest a distributed IoT service executed by them. SARA verifies both that each IoT device is not compromised (device trustworthiness), and that the exchanged communication data have not maliciously influence the communicating devices (legitimate operations). By tracing the execution order of each service invocation of an asynchronous distributed service, SARA allows each service to collect accurately historical data of its interactions, and transmits asynchronously such historical data to other interacting services. We have implemented and validated SARA through a realistic simulation on the Contiki emulator that demonstrates the functionality and efficiency of our protocol. The results confirm the suitability of SARA for low-end devices.