Fuzzing is arguably one of the most effective software vulnerability discovery techniques. However, despite recent advances, fuzzing stateful software suffers from severe inefficiencies and scalability limitations. This hinders automated testing for software that relies on state models, such as protocol implementations. Unlike stateless approaches, efficient stateful fuzzers need to i) explore the state model of the target system, ii) focus on the most interesting states, iii) track which messages are interesting for each state, and iv) handle expensive restarts and synchronizations of the system. In this paper, we present LibAFLstar, a fast and state-aware protocol fuzzer that addresses the aforementioned challenges leveraging i) partial message sequences, ii) a novel state scheduler, iii) state-aware queues and bitmaps, and iv) persistent mode. We fine-tune our approach by running an extensive ablation study with more than 20 configurations over six protocol implementations. Then, we evaluate LibAFLstar on the same protocol implementations (FTP, RTSP and HTTP) for 24 hours. We compare LibAFLstar’s performance with two state-of-the-art fuzzers: AFLNet and ChatAFL. Our experiments show that LibAFLstar is more than 30x faster than competitors and achieves, on average, 1.4x more coverage.