On 9 May 2012, Holst signed a new two-and-a-half-year Brøndby IF contract, which tied him to the club until the end of 2014. He made his Brøndby IF debut at the age of 17 as the youngest player ever in the club history when he was brought on for the final five minutes in the 5–1 away defeat against AGF on 13 May 2012. Daniel Stückler later became the youngest debutante for Brøndby IF during 2014.
2012–13 season
On 26 September 2012, Holst scored his first senior goal for Brøndby. It was the final goal in the 3–0 home win against the Danish first division side B93 in the DBU Cup. He was named man of the match for his performance in that game. His talent caught the attention from scouts all over Europe. Fellow Danish Superliga club FC Nordsjaelland reportedly tried to exploit Brøndby IF’s critical financial situation and offered €130,000 for the young starlet in the January 2013transfer window but Brøndby rejected the offer. Frederik Holst ended the 2012–13 season with 24 appearances, in which he was in the starting line-up 17 times, despite the fact that he formally belonged to Brøndby IF’s under-19 squad.
2013–14 season
Holst was officially promoted to the first team on 1 July 2013 and was handed jersey number 12. On 30 September 2013, he signed a new four-year contract which tied him to the club until the summer 2017. Holst had a good season with 30 appearances mostly as right-back, where he managed to push the newly signed Swedish international Michael Almebäck to a seat on the bench. His performance was crowned with a debut at the Danish U21 international team.
2014–15 season
On 31 July 2014, Holst made his Europa League debut when he was brought in for the final five minutes in the 3–0 away defeat against the Belgium side Club Brugge. In the first half of the season, he again managed to claim the position as right-back from former Swedish international Almebäck who was shipped off to Esbjerg fB on a one-year loan. Brøndby IF decided to give him another unseen challenge as they signed Elfsborgs captain and Swedish international Johan Larsson on a four-year contract during the winter transfer window. The addition of Larsson meant Holst competed with three right-backs as the under-19 and International starlet Svenn Crone was also included in the first team. Multiple rumours reported that Brøndby IF made a last hour offer to the fellow Superliga club SønderjyskE to add Holst on a loan for the rest of the season. SønderjyskE rejected the offer after serious consideration and instead Crone was sent on loan at Brønshøj BK.
2015–16 season
Holst started the season with a slot in the starting 11 as a central midfielder in a 9–0 home victory against the San Marino side A.C. Juvenes/Dogana in the Europa League qualification which he crowned by scoring his first European goal. Holst made a total of 30 appearances during the season, mainly as a substitute but all of them as a central midfielder in various roles.
2016–17 season
Holst had a positive start on the season being among newly signed manager Alexander Zorniger's chosen eleven in season opener against Esbjerg fB on 17 July 2016. He scored his first league goal when he completed a 4–0 home victory against Esbjerg fB, which was the best season opening in 15 years and the first season opening win in 8 years. He left the club at the end of the season, as his contract expired.
