Ольсен родился в Глострупе и начал карьеру в местном клубе с одноимённым названием в 1980 году. После того как он начал вызываться в молодёжную сборную, его подписал клуб первого датского дивизиона «Кёге». После четырёх сезонов, проведённых в низшей лиге, Ларс перешёл в «Брондбю». С новым клубом он пять раз выиграл чемпионат Дании, а также стал лучшим футболистом Дании в 1988 году[2]. Ольсен был капитаном «Брондбю» с 1987 по 1988 год. В 1991 году он перешёл в турецкий «Трабзонспор». В Турции Ольсен был основным футболистом команды и помог ей завоевать Кубок Турции. После того как Ларс покинул «Трабзонспор», он выступал за бельгийский «Серен» и швейцарский «Базель». В 1996 году Ольсен вернулся в «Брондбю», с которым в шестой раз стал чемпионом Дании. Последний матч за клуб сыграл в ноябре 1996 года[3].