Anja Feldmann studierte Informatik an der Universität Paderborn in Deutschland und schloss ihr Studium 1990 ab. Danach setzte sie ihr Studium an der Carnegie Mellon University fort, M.Sc. (1991), Ph.D. (1995). Die nächsten vier Jahre arbeitete sie als Postdoc bei AT&T Labs Research, bevor sie Forschungspositionen an der Universität des Saarlandes und der Technischen Universität München innehatte. Seit 2006 ist sie Professorin für Internet-Netzwerkarchitekturen an den Telekom Innovation Laboratories der Technischen Universität Berlin. Im Mai 2012 wurde sie als erste Frau auf Arbeitgeberseite in den Aufsichtsrat der SAP gewählt. Seit Anfang 2018 ist sie Direktorin am Max-Planck-Institut für Informatik in Saarbrücken.