An example method is provided in one example embodiment and includes receiving a packet of a session from a previous hop router at a service zone of a service chain; recording the previous hop router for the session; determining an appliance to service the packet in the service zone using load balancing; recording an appliance identity for servicing the session in the service zone; determining a next hop router in the service chain for the packet using load balancing; and recording the next hop router for the session.