Travel time information is crucial for Intelligent Transportation Systems (ITS). Taxis equipped with GPS tracking systems are one possible source for extracting travel time information. In this study, we present a framework for estimating travel time distributions on a city-scale network based on GPS trajectories of taxis. Our method is suitable for a very sparse data that does not contain information about individual link travel times. We test several approaches for estimating the marginal and network-wide joint distributions of travel time. We apply Gaussian copulas to address the non-Gaussianity of path travel time. We provide numerical results for a transportation network with 3174 links in Singapore based on GPS trajectories. For this network, the KullbackLeibler divergence for the proposed method is 0.58, whereas it is 0.6–0.74 for the baseline methods.