Lengauer studied Mathematics at the Free University of Berlin, earning his Diploma in 1975 and a Dr. rer. nat. (equivalent to a PhD) in 1976. Lengauer later gained an MSc (1977) and a PhD (1979) in computer science, both from Stanford University. He received his habilitation degree in computer science at Saarland University in 1984.^[3]

In the seventies and early eighties Lengauer performed research in Theoretical Computer Science at Stanford University, Bell Labs and Saarland University. In 1984 Lengauer became Professor of Computer Science at University of Paderborn. In the eighties and early nineties, Lengauer's research concentrated on discrete optimization methods for the design of integrated circuits and on packing problems in manufacturing. From 1992 to 2001 he was Professor of Computer Science at the University of Bonn and Director of the Institute for Algorithms and Scientific Computing at German National Center for Information Technology. Since 2001, he has been a Director of the Department on Computational Biology and Applied Algorithmics at the Max Planck Institute for Informatics.^[4]

With his Stanford PhD advisor Robert Tarjan, he is known for the Lengauer–Tarjan algorithm in graph theory.^[5]

Since the early 1990s his research has focused on computational biology, particularly the alignment of molecular sequences, and also the prediction of protein structure and function, and computational drug screening and design. On the latter topic he cofounded the company BioSolveIT GmbH in Sankt Augustin, Germany, together with Christian Lemmen, Matthias Rarey, and Ralf Zimmer from his team at GMD.^[6] Since 2000 he and his team have developed methods for analysis of viral resistance of HIV; in 2005 he entered the field of computational epigenetics.

Lengauer retired from his position as Director at Max Planck Institute for Informatics in 2018. Since 2019 he has been part-time affiliated with the Institute of Virology at Cologne University.

Lengauer has been the PhD advisor of over 50 students and coauthored over 350 publications.

Lengauer was a cofounder of the Conference Series European Symposium on Algorithms (ESA, 1993) and European Symposium on Computational Biology (ECCB, 2002). He was a member of the steering committee of the International Conference on Research in Computational Biology (RECOMB) from its inception in 1997 until 2010. He is a founding member of the International Society for Computational Biology (ISCB) and in 2014 became Vice President of this Society.^[7] He was elected as a Fellow of the ISCB in 2015.^[8] From January 2018 to January 2021 Lengauer was President of the ISCB.^[9]

In 2003, Lengauer was awarded the Konrad Zuse Medal, the highest award of the Gesellschaft für Informatik (German Informatics Society), as well as the Karl-Heinz-Beckurts Award. In 2010 he was awarded the AIDS Research Award of the Heinz-Ansmann Foundation, together with Rolf Kaiser and Marc Oette. In 2014 he received the Hector Science Award.^[10]

Lengauer has been a member of the German National Academy of Sciences Leopoldina since 2003. In 2006 he became the Speaker of the Section on Information Sciences of this Academy, in 2013 the Speaker of its Class of Natural Sciences, and in 2015 a Member of the Presidium of the Academy.

Lengauer has also been a member of acatech, the German Academy of Science and Engineering, since 2007 and of Academia Europaea since 2010.

Lengauer's twin brother Christian Lengauer was a Professor in the Faculty of Informatics and Mathematics at the University of Passau.^[11]