With the increasing adoption of embedded devices across industries, concerns about their security are rising. While fuzzing has proved effective for detecting vulnerabilities in embedded devices, existing approaches treat inputs as ‘single-shot’, whereas in reality firmware processes a stream of sequential messages (e.g., network packets). This lack of abstraction and message-awareness hinders the efficient exploration of deep, multi-message dependent code. Yet, leveraging message boundaries is challenging, since real-world protocols rely on variable-length, implicitly delimited messages, and firmware images lack explicit input format specifications. To address this problem, we introduce SteamFuzz, a novel message-aware firmware fuzzing approach. SteamFuzz dynamically infers message windows for each newly discovered input before adding it to the corpus. Then, SteamFuzz leverages message windows to (1) drastically minimize inputs—increasing throughput and focusing mutations on meaningful bytes—and (2) perform message-level mutations—exploring message-dependent code. We implement SteamFuzz and evaluate it on a diverse set of 40 firmware images, comparing its performance with state-of-the-art fuzzers. Our experimental results demonstrate that, thanks to the inferred message windows, SteamFuzz explores program behaviors more efficiently, reaching coverage faster and reaching code that existing tools miss, while generating significantly shorter inputs.