Born in the village of Råby, 20 km NE of Randers, Lars Elstrup made his senior debut for local club Randers Sportsklub Freja in 1982. Over the next four seasons, he became a proven goalscorer in Danish football's mostly 2nd highest divisions, and before the 1986 season Elstrup moved to the defending champions Brøndby IF. He played just seven league games for Brøndby, scoring twice, before he moved abroad to play for Dutch club Feyenoord. He played there for two years, but only scored nine goals for the Rotterdam outfit.