Methods and apparatus for implementing anycast flow stickiness in stateful sessions are described. For the first packet from a source device to an anycast group, a destination anycast endpoint is selected from the anycast group by a routing process via an algorithm that is specified for the anycast group. A record of the mapping of the source device to the destination anycast endpoint may be stored. Additional packets in the flow are routed to the same anycast endpoint as the first packet according to the stored information. Alternatively, a hashing technique may be used to route packets to an anycast endpoint. The packets may be encapsulated in an encapsulation format that includes network substrate routing information to the destination anycast endpoint; anycast forwarding decisions are made at the overlay network level and not at the network substrate level, and thus flow stickiness can be maintained.