Nadeshda Brennicke wurde am 21. April 1973 in Freiburg geboren. Von 1989 bis 1991 besuchte sie die Zinner Schauspielschule in München. Auf Empfehlung von Sönke Wortmann erhielt sie anschließend die Hauptrolle der Friseuse Tina in der Komödie "Manta – Der Film". Nach einem Ausflug in die Musikbranche als Mitglied des Duos "Charade" spielte sie Nebenrollen in Fernsehserien wie "Anwalt Abel" und Kinofilmen wie "Workaholic", aber auch die Hauptrolle in Christian Petzolds Debütfilm "Pilotinnen". 1998 folgte der Durchbruch als Kommissarin in der TV-Serie "Die Straßen von Berlin". Im Jahr 2000 erhielt sie den Adolf-Grimme-Publikumspreis für ihre Leistung in Dennis Gansels TV-Drama "Das Phantom".

Zwei Rollen in anspruchsvollen TV-Produktionen wie Dominik Grafs Zuhälter-Porträt "Hotte im Paradies" (2002), in dem sie die Prostituierte Jenny verkörpert, und dem BR-Polizeiruf 110 "Silikon Walli" (2002) in der Titelrolle, bringen ihr Nominierungen für den Deutschen Fernsehpreis ein. Im Kino spielt sie tragende Rollen in der Gaunerkomödie "Kanak Attak" (2000) und als rätselhafte Film-Noir-Schönheit in Robert Schwentkes Thriller "Tattoo" (2001), außerdem ist sie in Komödien wie "Basta. Rotwein oder Totsein" (2004) und "Die Bluthochzeit" (2005) zu sehen.

Ihre Wandlungsfähigkeit als Schauspielerin stellt Brennicke abermals als Polizistin in einer Ehekrise in Andreas Morells Episodenfilm "Unschuld" (2008) unter Beweis. Privat lebt Nadeshda Brennicke mit ihrem Sohn auf einem Bauernhof im Oderbruch und züchtet dort neben der Schauspielerei arabische Vollblüter.