An example method for bi-directional flow stickiness in a network environment is provided and includes receiving a packet of a flow from a source address in a network, and destined to a destination address outside the network, looking up a flow table for an entry corresponding to the flow, and caching a forward flow entry and a reverse flow entry in the flow table if the look up results in a miss, the forward flow entry indicating a routing lookup, and the reverse flow entry indicating a previous hop from which the packet was received to maintain a bi-directional flow stickiness. Some embodiments also include receiving another packet from the destination address outside the network destined to the source address in the network, and forwarding it to the previous hop listed in the reverse flow entry.