Nielsen begon zijn loopbaan bij HB Tórshavn en debuteerde bij BK Frem. In 2007 werd hij door Blackburn Rovers aangetrokken en in 2008 aan Motherwell verhuurd. Voor beide clubs kwam hij niet in actie. In 2009 maakte hij de overstap naar Manchester City waarvoor hij op 24 april2010 debuteerde in de wedstrijd tegen Arsenal. Hij werd ook verhuurd aan Wrexham in 2009 en Tranmere Rovers (2010 tot januari 2011). Op 7 december 2012 werd zijn contract bij Manchester City ontbonden.