A method and a router device for managing memory for network overlay routes with fallback route support prioritization may be provided. A network overlay route as a candidate network overlay route may be obtained at a router for storage in a memory. The memory may store a plurality of network overlay routes for forwarding user plane traffic in a network. An assessment for storage of the candidate network overlay route based on a priority level indicator of the candidate network overlay route may be performed. The priority level indicator may be indicative of a fallback route support level of the candidate network overlay route in the router. Based on the assessment, at least one of the following may be performed: adding the candidate network overlay route to the memory and refraining from adding the candidate network overlay route to the memory.