Anja Nissen nació es 6 de noviembre de 1995 en la ciudad australiana de Nueva Gales del sur. Sus padres emigraron a este país desde Dinamarc,a con 11 y 22 años de edad, por lo que siempre estuvo vinculada a este país, y tiene la doble nacionalidad. Nació y se crió en la propiedad de sus padres, a 77 km de Sydney, junto a una hermana mayor. Durante sus años escolares, que finalizó en 2013, ya mostró un gran interés por la música, y participó en un programa llamado Talent Development Program (TDP) , para promocionar jóvenes talentos, y gracias al cual ofreció sus primeros conciertos en su propia escuela y en el área en la que residía. 

Pero no sólo este programa le permitió actuaciones, ya que en el año 2008, con tan sólo 12 años de edad, participó en la tercera edición del talent-show Australia’s Got Talent, cantando The Circle of Life, del musical El Rey León. .  no llegaría a clasificarse para la final, pero esta sería la primera de numerosas intervenciones televisivas, incluyendo programas de gran éxito de la televisión australianda, como Young Talent Time,  o Mornings with Kerri-Anne. Anja manifestó que se basaba en múltiples influencias, de artistas como Patti LaBelle, Aretha Franklin, Céline Dion, Mariah Carey y Stevie Wonder

Su salto definitivo a la fama comenzó con su triunfo en la tercera edición de The Voice australiana. En las audiciones a ciegas, los cuatro coaches la escogieron y ella finalmente se decantó por el equipo de Will.I.Am., con el que acabaría ganando la competición. Con ello consiguió la firma con Universal Music Group. Tras su éxito, publicó su primer disco de estudio, llamado simplemente con su nombre, Anja Nilssen, con las canciones que había interpretado durante el programa, pero la falta de promoción que recibió por parte de las principales emisoras de música del país contribuyó a que el álbum pasase bastante desapercibido en el panorama musical. 

Sin embargo, la fama y popularidad de Anja seguían creciendo en Australia, y en el año 2013 consiguió el prestigioso Mo Award, otorgado desde 1975 por la Industria Musical y Artística de Australia para reconocer los logros de artistas en el mundo del espectáculo. Cabe destacar que estos galardones dejaron de entregarse en 2016, por lo que Anja fue uno de los últimos artistas en recibirlo.

En 2014  tuvo su primer gran éxito con su primer sencillo, titulado I’am so excited. Poco a poco fue abriéndose camino en las listas de venta. Su participación en el álbum We Love Disney de 2014, en el que interpretó A Dream is a Wissh Your Heart Makes, del musical Cinderella, contribuyó a que fuera conocida en su país.

En mayo de 2015 publicó un nuevo single, Anyone Who Had a Heart, que formó parte de una telenovela australiana de gran éxito en ese momento, Love Chile. Mäs tarde ese mismo año, en agosto de 2015, publicó su tercer single, Triumph, que dio a conocer en la edición del programa The Voice Australia de 2015, y fue visto por más de 1,6 millones de espectadores.  Actuó en 2014 en el certámen de villancicos de Melbourne y colabró en el un cd publicado en ese acontecimiento, con la canción Joy To The World. Paralelamente, se convirtió en la imagen de la marca de ropa y complementos Lyla & Co. 

Su relación con Dinamarca (familiar, emocional) siempre estuvo presente en su vida, de forma que en 2016 intentó representar a este país en Eurovision, compitiendo por primera vez en el Dansk Melodi Grand Prix con la canción Never Alone, compuesta por la ganadora de Eurovisión Emelie de Forest, aunque tuo que conformarse con el segundo puesto con el 36 % de los votos. El año siguiente, en 2017, al segundo intento se alzó con el triunfo en la preselección danesa con el tema Where I Am, del cual es coautora, y obteniendo un 64 % de los votos.  En el Festival que se celebró en Kyiv quedó encuadrada en la segunda semifinal, donde consiguió clasificarse en décima posición y por lo tanto acceder a la final del sábado. A pesar de un gran despliegue pirotécnico, el mayor en Eurovisión hasta esa fecha, se clasificó en una modesta vigésima posición, con 77 puntos. Posteriormente publicó un MP de seis temas, titulado cono su entrada eurovisiva, Where I Am. 

A partir de 2017, Anja se trasladó a Los Angeles, donde estudió Piano electrònico, y Teroia musical en el Instituto de Músicos de Hollywood. Con la pandemia de 2020, dejó de viajar con relativa frecuencia a Dinamarca para asentarse más en Estados Unidos, y publicó dos nuevos singles: If We Only Had Tonight, y  Can’t Do This.  Posteriormente, en el año 2023 publicó un nuevo MP con seis temas, titulado Same Room. 

A principios de 2025 Anja decidió regresar a Dinamarca, y se estableció en Copenhague. Uno de los motivos fue reunirse con su marido, el coach deportivo Daniel Pauk, con quien contrajo matrimonio en agosto de 2024. Durante varios años, la relación se mantuvo a través de viajes intercontinentales entre Dinamarca y California, y Anja manifestó que uno de sus objetivos era iniciar una nueva etapa a su lado. No ha abandonado su carrera musical, y en julio de 2025 participó en el Gay Pride de su nueva ciudad de residencia, interpretando su tema eurovisivo.