The first-principles density functional molecular dynamics simulations have been carried out to investigate the geometric, the electronic, and the finite temperature properties of pure Li clusters (Li10, Li12) and Al-doped Li clusters (Li10Al, Li10Al2). We find that the addition of two Al impurities in Li10 results in a substantial structural change, while the addition of one Al impurity causes a rearrangement of atoms. Introduction of Al impurities in Li10 establishes a polar bond between Li and nearby Al atom(s), leading to a multicentered bonding, which weakens the Li-Li metallic bonds in the system. These weakened Li-Li bonds lead to a premelting feature to occur at lower temperatures in Al-doped clusters. In Li10Al2, Al atoms also form a weak covalent bond, resulting in their dimerlike behavior. This causes Al atoms not to “melt” until 800K, in contrast to the Li atoms which show a complete diffusive behavior above 400K. Thus, although one Al impurity in Li10 cluster does not change its melting characteristics significantly, two impurities results in “surface melting” of Li atoms whose motions are confined around an Al dimer.