Frederiksen started his career in Frederikshavn fI, before moving to Viborg FF in 1989. He was an immediate success, and later he went on to become the top scorer of the Highest Danish League in 1993–1994 with 18 goals in 32 matches. He moved on to Silkeborg IF, and helped the club win the 1994 Superliga championship. As a result of the lack of playing time, he went back to Viborg in the following season. He then moved to league rivals Aalborg BK, and helped them win the 1999 Superliga title. In 2001, he moved back to Viborg. From 2003, he suffered a string of Achilles tendon injuries, and ended his career in 2005. At his retirement, the #22 shirt was retired by Viborg FF.
He went on to become head coach for Skive IK and later on assistant coach for Viborg FF. When Hans Eklund was fired in April 2009, Frederiksen was promoted to head coach. After the season he stepped down to become assistant for new manager Lars Søndergaard.