Some embodiments provide stateful services in a chain of services identified for some data messages. The edge forwarding element receives a data message at a particular interface of the edge forwarding element that is traversing the edge forwarding element in a forward direction between two machines. The edge forwarding element identifies (1) a set of stateful services for the received data message and (2) a next hop associated with the identified set of stateful services in the forward direction and a next hop associated with the identified set of stateful services in the reverse direction. Based on the identified set of services and the next hops for the forward and reverse directions, the edge forwarding element generates and stores first and second connection tracking records for the forward and reverse data message flows, respectively used to forward data messages received subsequently for the flow.