A method, computer program product, and data processing system for efficiently discovering and storing path MTU information in a sending host are disclosed. In a preferred embodiment, two path MTU tables are maintained. One path MTU table contains MTU values corresponding to the first-hop routers associated with the sending host. The other path MTU table contains MTU values corresponding to individual destination hosts. When the sending host needs to send information to a destination, it first consults the MTU table associated with individual destination hosts. If an entry for that destination host is found in the table, the sending host uses that MTU value. If not, the sending host consults the MTU table for the first-hop router on the path to the destination host and uses that MTU value. If that MTU value is too high, a new entry is made in the host-specific MTU table for the destination host.