Example methods are provided for a host to perform Media Access Control (MAC) address learning in a virtualized computing environment. The host includes multiple physical network interface controllers (NICs) configured as a team. The method may comprise: in response to detecting an egress packet that includes a source MAC address from a virtualized computing instance, learning address mapping information that associates the source MAC address with a virtual port; and sending the egress packet to a physical network via a first physical NIC selected from the team based on a NIC teaming policy. The method may also comprise: in response to detecting an ingress packet that also includes the source MAC address, determining whether the source MAC address has moved based on whether the ingress packet is received via the first physical NIC, or a second physical NIC from the team, but otherwise, maintaining the address mapping information.