Fuzzing is the de facto standard for automated testing. However, while coverage-guided fuzzing excels at code discovery, its effectiveness falters when applied to complex systems. One such class entails persistent targets whose behavior depends on the state of the system, where code coverage alone is insufficient for comprehensive testing. It is difficult for a fuzzer to optimize for state discovery when the feedback does not correlate with the objective. We introduce Tango, an extensible framework for state-aware fuzzing. Our design incorporates “state” as a first-class citizen in all operations, enabling Tango to fuzz complex targets that otherwise remain out-of-scope. We present state inference, a cross-validation technique that distills portable coverage metrics to reveal hidden path dependencies in the target. This in turn allows us to aggregate feedback from different paths while maintaining state-specific operation. We leverage Tango to fuzz stateful targets covering network servers, language parsers, and video games, demonstrating the flexibility of our framework in exploring complex systems. Using state inference, we shrink the scheduling queue of a fuzzer by around seven times by identifying functionally equivalent paths. We extend current state-of-the-art fuzzers, i.e., AFL++ and Nyx-Net, with state feedback from Tango. During our evaluation, fuzzers using our technique uncovered two new bugs in yajl and dcmtk.