A solution for tunnel path MTU discovery includes, at a first network device configured as an origination endpoint for a tunnel, storing a keep-alive packet having a size of an interface maximum transmission unit (MTU), the keep-alive packet indicating the packet should not be fragmented, the second network device configured as a termination endpoint for the tunnel. If the sending fails, the size of the keep-alive packet is iteratively changed to converge upon a path MTU, where the path MTU is the size of a largest keep-alive packet that can be sent from the first network device to the second network device without fragmentation.