Methods and systems for per-session NAT learning and firewall filtering are disclosed. Media packets associated with a call/session are received and processed at a media gateway. For the first few received media packets associated with a session, the media gateway uses various unique methods to learn the actual source IP address and UDP port assigned to the remote communication terminal by its customer-premises Network Address Translators (NATs) to the media flows of the current session. After the remote IP and UDP are learned, the media gateway reconfigures its firewall filtering function to check both the dynamically learned remote IP and UDP and the locally assigned IP and UDP of the current session. The per-session NAT learning function removes reachability issues in VoIP deployment, and the per-session firewall filtering function enhances security protection in VoIP deployment.