Anja Lechner wuchs in Neubeuern am Inn auf. Sie war Schülerin von Heinrich Schiff und studierte bei János Starker in Bloomington mit einem Stipendium der Studienstiftung des deutschen Volkes. 1980 gewann sie den Ersten Preis beim Bundeswettbewerb der Akademien und Konservatorien, und den Ersten Preis bei der Deutschen Phonoakademie. 1990 wurde sie mit dem Förderpreis der Stadt München ausgezeichnet. Die ARD produzierte 1992 ein Porträt von ihr.
Anja Lechner ist Gründungsmitglied des Rosamunde Quartetts, dem sie von 1992 bis zu seiner Auflösung 2009 angehörte und mit dem sie u. a. Werke von Joseph Haydn, Dmitri Schostakowitsch und Tigran Mansurjan aufnahm. Die Einspielungen bei ECM erhielten viele internationale Kritiken und zahlreiche Auszeichnungen.
Die Aufnahme leggiero, pesante mit Musik von Valentin Silvestrov wurde 2003 für einen Grammy nominiert.
Seit Anfang der 90er Jahre arbeitet sie mit dem argentinischen Bandoneonisten Dino Saluzzi in den verschiedensten Formationen zusammen. 2007 erschien ihre Duo-CD Ojos Negros, die auf einer viel beachteten USA-Tournee Anfang 2007 vorgestellt und vom Magazin Downbeat 2007 zur besten CD des Jahres gekürt wurde. Der Film „El Encuentro“ (Regie: Norbert Wiedmer und Enrique Roos) über das Duo Anja Lechner & Dino Saluzzi wurde 2013 vom Preis der Deutschen Schallplattenkritik ausgezeichnet.
Seit 2006 spielt Anja Lechner im Tarkovsky Quartet mit dem Pianisten und Komponisten François Couturier, dem Saxophonisten Jean-Marc Larché und dem Akkordeonisten Jean-Louis Matinier. Bis 2017 sind drei Alben des Quartets erschienen.
Seit 2012 spielen Anja Lechner und François Couturier auch im Duo. Das 2014 erschienene Album Moderato Cantabile bezeichnete Joachim Kronsbein im Nachrichtenmagazin Der Spiegel als „eines der ungewöhnlichsten Alben des Jahres“.[2]
