Fredrik Petersen begann in seiner Heimatstadt mit dem Handballspiel. Für den örtlichen Erstligisten IFK Ystad debütierte er auch in der schwedischen Elitserien. Mit seinem Verein zog Petersen 2004 ins Halbfinale der schwedischen Meisterschaft ein, sonst gehörte er aber eher zum Mittelmaß der Liga. 2006 wechselte Petersen zum dänischen Spitzenverein GOG Svendborg TGI, wo er als Nachfolger von Anders Eggert eingeplant war. Mit den Jütländern gewann er 2007 die dänische Meisterschaft. Im Februar 2010 wechselte er nach Bjerringbro-Silkeborg. Im Sommer 2012 wollte der Schwede zu AG København wechseln[4], schloss sich dann aber wegen der Insolvenz der Kopenhagener dem HSV Hamburg an,[5] mit dem er 2013 die EHF Champions League gewann. Zur Saison 2013/14 wechselte er zu den Füchsen Berlin, wo er einen Vertrag bis 2015 erhielt.[6] Mit den Füchsen gewann er 2014 den DHB-Pokal sowie 2015 den EHF Europa Pokal. Anfang Dezember 2015 wurde bekannt gegeben, dass Petersen Berlin im Sommer 2016 verlässt.[7] Mitte Dezember einigte er sich mit den Füchsen Berlin auf eine sofortige Vertragsauflösung.[8] Am 1. Februar 2016 verkündete HK Malmö Petersen unter Vertrag genommen zu haben.[9] Im Sommer 2018 kehrte er zum IFK Ystad zurück.[10] Zur Saison 2020/21 war ein Wechsel zum IFK Kristianstad vereinbart, jedoch wurde dieser Wechsel schon im Januar 2020 vollzogen.[11] Im August 2021 gab er sein Karriereende bekannt.[12]
Petersen ist seit August 2021 bei seinem Ausbildungsverein IFK Ystad als Jugendtrainer und als Sportdirektor tätig.[14] Am 11. Dezember 2021 bestritt Petersen sein Comeback für IFK Ystad.[15][16]
