Providing efficient mobility management in the current Internet becomes increasingly important due to the quick growth of wireless mobile users. The emerging Proxy Mobile IPv4 (PMIPv4) technique brings a possible solution for that purpose. Since NAT function is widely adopted in IPv4 environment nowadays because of lacking IPv4 addresses, the PMIPv4 interoperation with NAT must be considered. Unfortunately, owing to the possibility that private IP address may conflict, we encounter a problem in broadcastable point-tomultipoint wireless networks such as IEEE 802.11. To address this issue, we proposed a novel Network Address Translation on Demand (NAToD) scheme, which can well interoperate with the PMIPv4 solution. With our scheme, single public IPv4 addresses can be shared by multiple mobile nodes in the network, lowlatency handoff can be achieved, deployment cost can be reduced, and software upgrade can be avoided for WLAN mobile nodes. Our work allows mobile users in WLAN to access Internet based on the advantages of both PMIPv4 and NAT.