Methods, systems, and computer readable media for advertising network security capabilities are disclosed. According to one method, the method occurs at a network node. The method includes receiving a first route advertisement message that includes network security capabilities information indicating capabilities of a network security system associated with a route. The method also includes receiving a packet associated with a packet flow. The method further includes directing the packet associated with the packet flow to a downstream network node associated with the network security system.