Nahrstedt obtient un diplôme en mathématiques de l'Université Humboldt de Berlin en 1984 et une maîtrise en analyse numérique de l'Université Humboldt en 1985. Elle obtient un doctorat de l'Université de Pennsylvanie en 1995, sous la direction de Jonathan M. Smith[1]. Elle est rédactrice en chef de la revue Multimedia Systems (ACM et Springer) de 2000 à 2006 et présidente du groupe d'intérêt spécial ACM sur le multimédia de 2007 à 2013[2],[3].
En 2012, Nahrstedt est élue Fellow de l'Association for Computing Machinery "pour ses contributions à la gestion de la qualité de service pour les systèmes multimédias distribués"[4],[3]. Elle est membre de l'Institute of Electrical and Electronics Engineers et lauréate d'un IEEE Computer Society Technical Achievement Award 2012 "pour ses contributions pionnières à la qualité de service de bout en bout et à la gestion des ressources dans les réseaux filaires et sans fil"[2]. En 2013, elle devient membre de l'Académie allemande des sciences Leopoldina[5],[6]. En 2022, elle est élue à la National Academy of Engineering des États-Unis[7].