Two-factor authentication, pervasively used in Internet services such as online banking, is an essential tool to corroborate entity identities in the Internet, which is also increasingly demanded in the Internet of Things (IoT) and sensor networks. However, the resource constraint of a typical IoT device generally forbids direct application of existing two-factor authentication schemes, especially when such a device acts as the verifier to verify the identity of another entity (known as the prover). This paper proposes a lightweight two-factor entity authentication protocol with a novel second factor for the IoT. In addition to the conventional first factor, namely, a password/shared secret key, the history of the data exchanged between the prover and verifier is used as the second factor. In order to pass the verifier’s authentication, the prover must have access to the shared key and practically all the historical data received from the verifier. Leveraging on the data retrieval and searching capability of contemporary big data technologies, the proposed second authentication factor is practically efficient while achieving attractive properties such as scalability and increasing robustness, in addition to relaxed resource requirements on the verifier. The proposed scheme demonstrates a tradeoff between security and computational overhead, and such scalability particularly suits for the IoT, with devices of diverse capabilities. Besides, while the prover needs to know all the historical data in order to pass the authentication, the verifier does not have to keep any data — thus different from the trivial scenario using multiple passwords/shared secret keys as the second factor.