Century-long disposal of sewage sludge in Mitchell Lake at San Antonio, Texas has resulted in hyper-eutrophic conditions and excess accumulation of toxic metals in the lake system. To identify the most suitable remedial measure for Mitchell Lake, a baseline study of metal geochemistry in lake water and sediments is currently in progress. The primary objectives of this study are to establish the role of sediment physico-chemical properties in the release of heavy metals into the lake water. The sediment samples were collected from 12 strategic locations. Samples were characterized for their physico-chemical properties for total concentrations of common sludge metals, such as Cd, Co, Cr, Cu, Fe, Mn, Ni, Pb, and Zn. To quantify the amount of potentially bioavailable heavy metal concentrations, two widely used chemical extraction schemes, namely, the Mehlich III method and the Olsen method were used. Total and bioavailable concentrations of metals were correlated with the physicochemical properties of lake sediments. The results showed that Mehlich III method extracted the largest amount of metals, but being an acid extraction method it overestimated the potentially bioavailable fraction of metals from the sediment. The Olsen method, which employs an alkaline extraction scheme, was deemed most suitable for determining metal bioavailability under the specific geochemical conditions of Mitchell Lake. The results also indicated that bioavailability of heavy metals in the contaminated sediments of Mitchell Lake is largely controlled by the geochemical properties at the sediment-water interface. Hence, careful evaluation of the physicochemical properties of sediments is necessary prior to deciding on the most appropriate remedial measure.