Born in Ninove, Van der Elst started his professional career at R.W.D. Molenbeek, earning his first call-up for Belgium in 1982. Two years later, he moved to Club Brugge K.V. and stayed there until he finished his career in 1999, going on to total over 500 overall appearances with the side (466 in the league alone). During four seasons, he often partnered in midfield his namesake Leo – no relation.
Van der Elst won the Golden Shoe twice in his career, an accomplishment for an eminently defensive-minded player. He also appeared in four FIFA World Cups from 1986 to 1998, only scoring once for his country in nearly 90 matches, in a 2–2 friendly draw against Norway on 25 March 1998.
In 2005 Van der Elst returned to 'his' Club Brugge, as an assistant, joining former teammates – both in club and country – Jan Ceulemans, Marc Degryse, Dany Verlinden and René Verheyen. He remained with the team when Verheyen and Ceulemans were fired in 2006, but was eventually shown the door the following year, with head coach Emilio Ferrera.