Estimating temporal patterns in travel times along road segments in urban settings is of central importance to trac engineers and city planners. In this work, we propose a methodology to leverage coarse-grained and aggregated travel time data to estimate the street-level travel times of a given metropolitan area. Our main fo- cus is to estimate travel times along the arterial road segments where relevant data are often unavailable. The central idea of our approach is to leverage easy- to-obtain, aggregated data sets with broad spatial cov- erage, such as the data published by Uber Movement, as the fabric over which other expensive, fine-grained datasets, such as loop counter and probe data, can be overlaid. Our proposed methodology uses a graph representation of the road network and combines sev- eral techniques such as graph-based routing, trip sam- pling, graph sparsification, and least-squares optimiza- tion to estimate the street-level travel times. Using sampled trips and weighted shortest-path routing, we iteratively solve constrained least-squares problems to obtain the travel time estimates. We demonstrate our method on the Los Angeles metropolitan-area street network, where aggregated travel time data is available for trips between traffic analysis zones. Additionally, we present techniques to scale our approach via a novel graph pseudo-sparsification technique.