Auteur de romans, nouvelles, poésies, théâtre, Hervé Le Tellier est aussi l'auteur de formes très courtes, souvent humoristiques, dont ses variations sur la Joconde. Il a été coopté à l'Oulipo (Ouvroir de Littérature Potentielle) en 1992 (simultanément au poète allemand Oskar Pastior), et a publié sur l'Ouvroir un ouvrage de référence : Esthétique de l'Oulipo. Il a participé à l'aventure de la série « Le Poulpe », avec un roman, La Disparition de Perek, adapté également en bande dessinée.
Mathématicien de formation, longtemps militant de la Ligue communiste révolutionnaire où il fréquente Daniel Bensaïd, Julien Dray, Jean-René Chauvin et Edwy Plenel, puis journaliste — diplômé du Centre de formation des journalistes à Paris (promotion 1983) — il est linguiste et spécialiste des littératures à contraintes. Éditeur, il a fait publier plusieurs ouvrages au Castor Astral comme What a man !, de Georges Perec, et Je me souviens de « Je me souviens », de Roland Brasseur.
Avec d'autres artistes et écrivains, comme Henri Cueco, Gérard Mordillat, Jacques Jouet, et Jean-Bernard Pouy, il participe depuis 1991 à l'émission Des Papous dans la tête animée par Françoise Treussard sur France Culture, ainsi qu'à l'émission de Caroline Broué, « La Grande Table ».
Chroniqueur dans les années 90 sous le pseudonyme de "Docteur H" à La Grosse Bertha, qui refondera bientôt Charlie Hebdo, il collabore quotidiennement, depuis 2002, à la lettre électronique matinale du journal Le Monde, par un billet d'humeur intitulé Papier de verre, ainsi qu'à la revue Nouvelles Clés, où il anime depuis 2009 la page Retrouver du non-sens.
Il est enfin, avec Frédéric Pagès, journaliste au Canard enchaîné, l'un des fondateurs des Amis de Jean-Baptiste Botul (1896-1947), philosophe fictif de tradition orale.
En 2011, Frédéric Cherboeuf met en scène le recueil Les Amnésiques n'ont rien vécu d'inoubliable au Lucernaire avec Etienne Coquereau et Isabelle Cagnat.
Il a reçu en 2013 le Prix de l'Humour noir pour sa traduction (factice) des Contes Liquides de Jaime Montestrela, un auteur portugais dont il a inventé l'œuvre et la biographie.