A pseudorandom number generator is an important component for implementing security functionalities on RFID tags. Most previous proposals focus on true random number generators that are usually inefficient for low-cost tags in terms of power consumption, area, and throughput. In this contribution, we propose a lightweight pseudorandom number generator (PRNG) for EPC Class-1 Generation-2 (EPC C1 Gen2) RFID tags. The proposed PRNG fully exploits nonlinear feedback shift registers and provides 16-bit random numbers that are required in the tag identification protocol of the EPC C1 Gen2 standard. The generated sequences are able to pass the EPC C1 Gen2 standard’s statistical tests as well as the NIST randomness test suite. Moreover, a detailed cryptanalysis shows that the proposed PRNG is resistant to the most common attacks such as algebraic attacks, cube attacks, and time-memory-data tradeoff attacks. In particular, the proposed PRNG can be implemented on low-cost Xilinx Spartan-3 FPGA devices with 46 slices.