Methods, systems, and apparatuses for discovering dynamic path maximum transmission unit (PMTU) between a sending computing device and a receiving computing device (e.g., a client device and a host device) are described herein. A sending computing device may iteratively transmit bursts of probe packets, each burst being defined by a search range between a maximum packet size and a minimum packet size. The sending computing device may iteratively update the search range based on the previous iteration until the search converges on the PMTU. When the PMTU is discovered, each of the computing devices may update their transport and presentation layer buffers based on the discovered PMTU without any other protocol level disruption. In a multi-path scenario, the computing device may discover PMTU for each of the paths and select a performance optimal path based on the individual PMTUs and other network characteristics such as loss, latency, and throughput.