Nicolaï studied law and political science at the Free University Amsterdam. He was a member of the House of Representatives between 1998 and 2002, in 2003, and again from 2006 to 2011. From 2002 to 2006, he was deputy government minister, and from 2006 to 2007 government minister.