Nikolai Frederiksen speelde in de jeugd van Næsby BK en FC Nordsjælland, waar hij op 27 september 2017 in de met 0-4 gewonnen bekerwedstrijd tegen Vejgaard BK zijn debuut maakte. Bij zijn competitiedebuut op 14 oktober 2017, in de met 3-2 gewonnen thuiswedstrijd tegen Randers FC, scoorde hij het winnende doelpunt. Met Nordsjælland eindigde hij derde en kwalificeerde hij zich voor de voorrondes van de Europa League. In de zomer van 2018 vertrok hij voor een bedrag van 1,25 miljoen euro naar Juventus FC, waar hij in het tweede elftal speelt. In de winterstop van het seizoen 2019/20 werd hij voor een half jaar verhuurd aan Fortuna Sittard.[3] Hij speelde twee wedstrijden voor Fortuna, waarna de competitie werd beëindigd vanwege de coronapandemie. In het seizoen 2020/21 wordt hij aan het Oostenrijkse WSG Swarovski Tirol verhuurd. Op 14 juli 2021 tekende hij een driejarig contract bij Vitesse, met een optie voor nog een jaar.[4] Eind januari 2023 werd Baden Frederiksen voor een jaar verhuurd aan Ferencváros, met optie tot koop.[5]
In februari 2024 kondigde Vitesse aan dat de wegen tussen club en speler gingen scheiden.[6] Hij ging aan de slag in de Deense Superliga bij Lyngby BK.[7]