A method, apparatus and system for providing stateful service function paths with redundancy are provided. Multiple instances of a service function path are included, each with at least one instance of a stateful service function. The redundant stateful service functions transmit messages between one another to so that the current state is synchronized. Upon failure of a service function in a first instance of the service function path, packets are redirected to a backup associated with the failed service function located in another instance of the service function path. Once processed by the backup service function, the redirected packets may be routed back to the first instance of the service function path.