Paillou et al. (2009) mapped a 900 km-long paleodrainage system in eastern Libya, the Kufrah River, that could have linked the southern Kufrah Basin to the Mediterranean coast through the Sirt Basin, possibly as long ago as the Middle Miocene. We study here the potential connection between the terminal part of the Kufrah River and the Mediterranean Sea through the Wadi Sahabi paleochannel, which may have constituted the northern extension of the lower Kufrah River paleodrainage system. New analysis of SRTM-derived topography combined with Synthetic Aperture Radar images from the Japanese PALSAR orbital sensor allowed the mapping of seven main paleochannels located west of the Kufrah River, each of which is likely to have formed a tributary that supplied water and sediment to the main paleodrainage system. The northernmost four paleochannels probably originated from the Al Haruj relief, a Pliocene alkaline basaltic intracontinental volcanic field, and potentially connected to the Wadi Sahabi paleochannel. The remaining three paleochannels are in the more southerly location of the Sarir Calanscio, North-East of the Tibesti mountains, and barely present a topographic signature in SRTM data. They end in the dunes of the Calanscio Sand Sea, forming alluvial fans. The most southern paleochannel, known as Wadi Behar Belama, was previously mapped by Pachur (1996) using LANDSAT-TM images, and was interpreted by Osborne et al. (2008) as representing part of an uninterrupted sediment pathway from the Tibesti mountains to the Mediterranean Sea. Processing of SRTM topographic data revealed local depressions which allow to connect the seven paleochannels and possibly the terminal alluvial fan of the Kufrah River to the Wadi Sahabi paleochannel, through a 400 km-long, south-north oriented, paleocorridor. These new findings support our previous hypothesis that proposed a connection between the lower Kufrah River in the region of the Sarir Dalmah and the Wadi Sahabi paleochannel, which connected to the Mediterranean Sea. Including the newly mapped paleochannels, the Kufrah River paleowatershed, at its maximum extent, would have covered more than 400,000 km2, representing close to a quarter of the surface area of Libya.