The Mishna Berura (317:16) cites the Magen Abraham (Rav Abraham Gombiner, Poland, 1637-1682) who rules that one should not lace a new shoe for the first time on Shabbat. This would constitute a violation of "MeTaken Manah"-fixing a utensil. Hacham Ovadia concurred with this ruling, although he did cite a ruling of Hacham Yosef Massas who was lenient, since today, the shoe is wearable even without the laces. Hacham Bension and the Menuhat Ahaba were also strict.
There is no problem re-lacing an old shoe. However, the Poskim discuss whether it is permitted to re-lace an old shoe with new laces. The Mishna Berura (317:17) cites the Elyah Rabba (R. Eliyahu Spira, 1660–1712, Prague) who is strict. On the other hand, Hacham Ovadia and Menuhat Ahaba are lenient. They argue that there is no difference between old laces and new laces in this regard.
The Rema (317:2) rules that one may not even thread a string that is usually tied, out of concern that one may tie a knot to prevent it from becoming unthreaded. For example, it is prohibited to thread a pearl that fell off a necklace out of fear that she may tie a knot at the end of the strand to keep the pearls in place. Hacham Ovadia (Hazon Ovadia Vol. 4) and Shemirat Shabbat K’hilhata rule in accordance with the Rema’s opinion.
SUMMARY
It is prohibited to lace new shoes for the first time, but old shoes may be re-laced with new (or old) strings.
It is prohibited to string pearls on Shabbat, even without tying the ends.
