Consumption of multimedia content is moving from a residential environment to mobile phones. Optimizing Quality of Experience—smooth, quick, and high quality playback—is more difficult in this setting, due to the highly dynamic nature of wireless links. A key requirement for achieving this goal is estimating the available bandwidth of mobile devices. Ideally, this should be done quickly and with low overhead. One challenge is that the majority of connections on mobiles are short-lived TCP connections, where a significant portion of data exchange is within the slow start phase. In this paper, we propose a novel method that passively estimates the currently available bandwidth by monitoring the minimal traffic generated by such connections. To the best of our knowledge, no other solution can operate with such constrained input. Our estimation method is able to achieve good precision despite artifacts introduced by the slow start behavior of TCP, mobile scheduler and phone hardware. We evaluate our solution against traces collected in 4 European countries. Furthermore, the small footprint of our algorithm allows its deployment on resource limited devices.