We have studied the low temperature phases of Pb/Ge(111) at Pb coverages Θ=1/3, 1, and 4/3 using ab initio molecular dynamics. Stable phases are found to occur at Θ=1/3 and 4/3. For the low-coverage (Θ=1/3) α phase, we confirm the model of Pb atoms adsorbed at T4 sites of the Ge(111) substrate. For the high coverage (Θ=4/3) β phase and very low temperature, we determine a structure characterized by the presence of covalently bonded Pb chains parallel to 〈11¯0〉 substrate directions. At room temperature, fluctuations are found to disrupt long-range Pb chains and restore the threefold symmetry of the ideal Ge(111) surface. The calculated structure factors and local density of states agree well with x-ray diffraction and STM data.