É filho dos imigrantes poloneses Isai Leirner, que foi diretor do Museu de Arte Moderna de São Paulo e fundador da Galeria de Arte da Folha de S.Paulo e do Prêmio Leirner de Arte Contemporânea, e de Felícia Leirner, escultora; irmão de Giselda Leirner, desenhista; tio de Sheila Leirner, crítica de arte.
Viveu de 1947 a 1952 no Estados Unidos, onde estudou engenharia têxtil, mas sem concluir o curso. Entre 1956 e 1958, estuda artes plásticas. De volta ao Brasil, faz sua primeira exposição individual no ano de 1961, em São Paulo
Em 1966, funda e integra o Grupo Rex, ao lado de Wesley Duke Lee, Carlos Fajardo e Geraldo de Barros, Frederico Nesser e José Resende. Tempos depois, Olivier Peroy e Roland Cabot aderem ao grupo. O grupo lança o jornal Rex Time e cria a Rex Gallery & Sonss. Em 1967 é premiado na XX Bienal de Tóquio. Em seu trabalho realiza comentário irônico acerca do sistema de arte.
Leirner tem participado de várias exposições no Brasil e no exterior. Em 1997, muda-se para o Rio de Janeiro e passa a dar aulas na Escola de Artes Visuais do Parque Lage. Vive e trabalha no Rio de Janeiro.
Nelson é considerado um artista polêmico, com sua preocupação constante em sua trajetória artística, ele busca atingir as ruas de forma a criar indagações nas pessoas, para conseguir isso ele utiliza várias estratégias estéticas e/ou comportamentais de forma experimental, mesmo que isso cause estranhamento às pessoas. Tornou-se hoje um dos mais expressivos representantes do espírito vanguardista dos anos 60, tanto no Brasil, quanto no mundo. Sua ideia central é popularizar o objeto de arte e introduzir a participação do público. Uma das características de Nelson são as críticas irônicas ao sistema de arte.
Leirner se recusou a participar das Bienais de 1969 e 1971 durante o período da ditadura. Já no ano de 1974, criticou o regime militar através da série A rebelião dos Animais. No ano de 1998, uma série de trabalhos de Leirner (com intervenções em fotografias de crianças da fotógrafa neozelandesa Anne Geddes) foi censurada pelo juizado de menores do Rio de Janeiro, essa atitude do juizado provocou um movimento de artistas contra a censura nas artes. No ano de 2003, a galeria Brito Cimino iniciou uma exposição chamada Fora de Moda, onde o artista expôs algumas de suas obras. Com temas populares, coisas comuns, objetos que costumamos ver nas feiras e em lojas da 25 de março, além de penduricalhos que o artista transforma em procissões descoloridas. A exposição tinha um ar divertido e irônico, mas longe de ser apenas brincadeira de criança.
No mês de maio de 2007, Nelson Leirner expôs trabalhos inéditos no Rio de Janeiro, a exposição denominada Obras Inéditas na Silva Cintra Galeria de Arte contou com instalações no chão e paredes inéditas, um exemplo foi a instalação em que sacis jogavam tênis e a série Time [r] is money, criadas com mapas e despertadores. Foram 15 trabalhos no total, e todos com a mesma tradição de contestação, ironia e humor das obras de Leirner.
Nelson Leirner esteve em parceria com a Absolut Vodka. O projeto tem como objetivo criar uma releitura da garrafa utilizando a visão que o artista tem da marca. No total doze artistas brasileiros fazem parte do projeto que tem como temática a cultura brasileira.
Nelson Leirner morreu no dia 7 de março de 2020, em sua casa, no Jardim Botânico, zona sul do Rio de Janeiro.
