Roughly described, a header processing engine for a network interface device has a header recognizer to parse the headers of a data packet stored at a buffer to identify the type and position of each header in the packet; a constructor unit; and a processor including an execution pipeline. The header recognizer is configured to, for each header: select in dependence on the header type commands stored at a command memory; and form one or more messages for the constructor unit identifying the selected commands and the position of the header in the data packet. The commands selected for the packet headers are collectively such as to, if executed by the constructor unit, cause the constructor unit to generate a data structure which operates to cause the processor to process of the packet headers without accessing the data packet at the buffer.