An apparatus to perform hardware-based lossless stateful signature matching is disclosed. In one embodiment, the apparatus comprises a memory and multiple finite state machine (FSM) comparison units operating in parallel to compare packets to signatures to identify matches, if any, between data units in the packets and the plurality of signatures. Each of the FSM comparison units include FSMs having states stored in the memory and at least one transition between pairs of states, and a transition to a new state results in a non-destructive additive operation being performed to store any previous state with the new state.