Example methods are provided for a first host to perform packet flow information invalidation in a software-defined networking (SDN) environment. One example method may comprise learning packet flow information based on one or more packets from a second host, the packet flow information being stored in association with a packet flow information identifier assigned to the second host. The method may further comprise: in response to detecting, from a third host or management entity, a notification indicating a network topology change that involves the second host, determining the packet flow information identifier assigned to the second host based on the notification; and invalidating the packet flow information stored in association with the packet flow information identifier.