The subglacial Lake Vostok may be a unique reservoir of genetic material and it may contain organisms with distinct adaptations, but it has yet to be explored directly. The lake and the overlying ice sheet are closely linked, as the ice-sheet thickness drives the lake circulation, while melting and freezing at the ice-sheet base will control the flux of water, biota and sediment through the lake. Here we present a reconstruction of the ice flow trajectories for the Vostok core site, using ice-penetrating radar data and Global Positioning System (GPS) measurements of surface ice velocity. We find that the ice sheet has a significant along-lake flow component, persistent since the Last Glacial Maximum. The rates at which ice is frozen (accreted) to the base of the ice sheet are greatest at the shorelines, and the accreted ice layer is subsequently transported out of the lake. Using these new flow field and velocity measurements, we estimate the time for ice to traverse Lake Vostok to be 16,000-20,000 years. We infer that most Vostok ice analysed to date was accreted to the ice sheet close to the western shoreline, and is therefore not representative of open lake conditions. From the amount of accreted lake water we estimate to be exported along the southern shoreline, the lake water residence time is about 13,300 years.