Τα δυο πρώτα χρόνια της ζωής του τα πέρασε στις Φυλακές Αβέρωφ με τη μητέρα του, που είχε φυλακιστεί ως πολιτική κρατούμενη.Το 1958 ξεκίνησε μαθήματα κιθάρας στο Εθνικό Ωδείο με καθηγητή τον Δημήτρη Φάμπα και πήρε το δίπλωμα το 1969 με Άριστα. Το 1970 εγκαταστάθηκε στην Ιταλία, όπου του ανατέθηκε η έδρα κλασικής κιθάρας στη Scuola Ciciva di Milano, στην οποία δίδαξε ώς το 1975. Το 1970 επίσης παρακολούθησε τα μαθήματα της Ακαδημίας Santiago de Compostella στην Ισπανία με τον Jose Tomas. Το 1975 εγκαταστάθηκε οριστικά στην Αθήνα και από αυτή τη χρονιά δίδαξε κλασική κιθάρα στο Εθνικό Ωδείο. Τα έτη 1975, 1977 και 1979 έδωσε ρεσιτάλ στο Φεστιβάλ Κλασικής Κιθάρας του Esztergom της Ουγγαρίας. Το 1978 πήρε μέρος στο διεθνές Φεστιβάλ Πολιτικού Τραγουδιού στο Ανατολικό Βερολίνο και στο 11ο Παγκόσμιο Φεστιβάλ Νεολαίας στην Αβάνα της Κούβας. Ως συνθέτης και σολίστ έχει δώσει πολλά ρεσιτάλ σε πολλές χώρες (Ελλάδα, Ιταλία, Φινλανδία, Ελβετία, Γερμανία, Ουγγαρία, Αυστρία, Κούβα). Ως καθηγητής στο Εθνικό Ωδείο Αθήνας, είχε μαθητές αρκετούς δημοφιλείς καλλιτέχνες όπως οι Μανώλης Ανδρουλιδάκης, Σωκράτης Μάλαμας, Παναγιώτης Μάργαρης, Γιώργος Μελάς, Λάμπρος Ντούσικος, Δημήτρης Σωτηρόπουλος, κ.ά.. Από το 1994 ανέλαβε καθήκοντα προέδρου στη Στέγη Γραμμάτων και Τεχνών του Υπουργείου Πολιτισμού και από το 1995 ανέλαβε καλλιτεχνικός διευθυντής στο διεθνές Φεστιβάλ της Πάτρας (από το 1999 τη θέση κατέχει ο Αλέξανδρος Μυράτ).
Ο Νότης Μαυρουδής τραυματίστηκε θανάσιμα στις 3 Ιανουαρίου 2023 έπειτα από πτώση από ύψος τριών μέτρων στο σπίτι του στην τοποθεσία Κουκουράβα, στη Μακρινίτσα Μαγνησίας.Το 1965 κατέκτησε το Α΄ βραβείο στο 4ο Φεστιβάλ Τραγουδιού Θεσσαλονίκης, με το τραγούδι «Ήταν μεγάλη η νύχτα» (στίχοι: Γιάννης Κακουλίδης, ερμηνεία: Σούλα Μπιρμπίλη).
Το 1969 τιμήθηκε με το Α΄ βραβείο στον διεθνή διαγωνισμό κιθάρας στο Μιλάνο, και το βραβείο του ιταλικού μουσικού Τύπου “Mario de Luigi”.
Το 1990 βραβεύτηκε στον διεθνή διαγωνισμό παιδικού τραγουδιού στη Λισαβόνα. Την ίδια χρονιά η πρεσβεία της Βραζιλίας στην Ελλάδα του απένειμε το βραβείο «Heitor Villa-Lobos» για την προσφορά του στη διάδοση του έργου του Βραζιλιάνου συνθέτη στην Ελλάδα.
Την ίδια χρονιά, το τραγούδι του «Ο παλιάτσος» με την παιδική χορωδία του Δημήτρη Τυπάλδου, πήρε το Α΄ βραβείο στον 12ο διεθνή Διαγωνισμό Παιδικών Χορωδιών στη Λισαβόνα.
Το 2005 και 2006 του απονεμήθηκε το βραβείο «Αρίων» για τους δίσκους Cafe de l’ art – Cinema και Cafe de l’ art – Τσιτσάνης – Βαμβακάρης.
Ο Νότης Μαυρουδής εισήλθε στη δισκογραφία το 1964 με τα τραγούδια «Άκρη δεν έχει ο ουρανός» και «Τα γιορτινά σου φόρεσε», σε στίχους του Γιάννη Κακουλίδη με ερμηνευτή τον Γιώργο Ζωγράφο. Το 1966 έγραψε μουσική για το θέατρο και τον κινηματογράφο.
Το 1968 μελοποίησε το έργο του του Οδυσσέα Ελύτη Άσμα ηρωϊκό και πένθιμο για τον χαμένο Ανθυπολοχαγό της Αλβανίας, που είναι ένα λαϊκό ορατόριο για φωνή-χορωδία και ορχήστρα.
Το 1976 κυκλοφόρησε τον δίσκο Ζωγραφιές απ’ τον Θεόφιλο σε στίχους του Άκου Δασκαλόπουλου, εμπνευσμένους από τις ζωγραφιές του Θεόφιλου.
Το 1977, μελοποίησε ποιήματα του Μάνου Χατζιδάκι στον δίσκο Παιδί της Γης.
Το 1985 κυκλοφόρησε τον δίσκο Έρως ανίκατε μάχαν σε ποίηση του Ηλία Πετρόπουλου.
Από το 1990 έχει γράψει τραγούδια για Παιδική Χορωδία, και συνεργαζόταν με την Παιδική Χορωδία Δημήτρη Τυπάλδου.
Το 1998 κυκλοφόρησαν οι δίσκοι με μουσική για τις θεατρικές παραστάσεις «Όλιβερ Τουίστ» (με μουσική και τραγούδια του για την παράσταση του «Θιάσου 81»), και «Ιφιγένεια εν Αυλίδι» (με μουσική και 3 τραγούδια, για την παράσταση της ομώνυμης τραγωδίας από τον Θίασο «Θυμέλη»).
Μεταξύ 1999-2008 ηχογράφησε μαζί με τον μαθητή του Παναγιώτη Μάργαρη τη βραβευμένη σειρά Cafe de l’ art, στην οποία διασκεύαζαν γνωστά τραγούδια από το ελληνικό και διεθνές ρεπερτόριο, για δύο κιθάρες. Στο ίδιο πνεύμα, το 2018 ξεκίνησε τη σειρά Café Latino με τον Γιώργο Τοσσικιάν.
Το 2019 κυκλοφόρησε από τις εκδόσεις IANOS το έργο “Άγρυπνο φεγγάρι”, Μελοποιημένοι Έλληνες ποιητές από τον 19ο και τον 20ό αιώνα.
Το 1999 κυκλοφόρησε τον δίσκο Λούνα Πάρκ, με την Παιδική Χορωδία του Δημήτρη Τυπάλδου και συμμετοχή του Γιώργου Νταλάρα. Το 2002 συνέθεσε τραγούδια για γυναικείες φωνές, στον δίσκο Στην ηχώ του έρωτα, στον οποίον συμμετέχουν μεγάλα ονόματα όπως η Χάρις Αλεξίου, η Γλυκερία, η Ελευθερία Αρβανιτάκη, η Έλλη Πασπαλά. Το 2006 έγραψε από κοινού με τον Ηλία Κατσούλη τραγούδια που «αφηγούνταν» τις ιστορίες μεγάλων ελλήνων καλλιτεχνών (Γρ. Μπιθικώτσης, Στ. Χασκήλ, Ρόζα Εσκενάζυ, Μαρίκα Νίνου, Φλέρυ Νταντωνάκη, Σωτηρία Μπέλλου κ.ά.) και κυκλοφόρησαν στον δίσκο Carte Postale.
Ο Νότης Μαυρουδής έχει συνεργαστεί με σπουδαίους ποιητές όπως ο Οδυσσέας Ελύτης, ο Γιάννης Κακουλίδης, ο Ηλίας Πετρόπουλος, ο Άκος Δασκαλόπουλος, Μάνο Χατζιδάκι, και τραγουδιστές όπως Θανάσης Γκαϊφύλλιας, Γιώργο Ζωγράφο, Αρλέτα, Πόπη Αστεριάδη, Ελένη Βιτάλη, Γιώργο Μουφλουζέλη, Γιάννη Σαμσιάρη, Νένα Βενετσάνου, Πέτρο Πανδή, Κώστα Θωμαΐδη, Σταμάτη Κραουνάκη, Τάνια Τσανακλίδου, Μανώλη Μητσιά, Χάρις Αλεξίου, Γιώργο Νταλάρα, Γλυκερία, Παντελή Θαλασσινό, Έλλη Πασπαλά, Αναστασία Μουτσάτσου κ.ά..
Ως τραγουδιστής συμμετείχε σε ένα μόνο τραγούδι, το «Πόλη Κωνσταντινούπολη» από τον δίσκο Εάλω η Πόλις, όπου όλοι οι συνθέτες ερμήνευσαν τα τραγούδια τους. Ακόμα, συμμετείχε ως δεύτερη φωνή σε πέντε (5) τραγούδια στον δίσκο Μικρές νυχτερινές μουσικές.
Από τις εκδόσεις Γαβριηλίδης, κυκλοφόρησε το βιβλίο του Περί ελληνικού τραγουδιού το ανάγνωσμα με ένα ένθετο cd στο οπισθόφυλλο «Με δανεικά ιδανικά» που περιλαμβάνει επτά νέα τραγούδια του.
Το 2002 ο Νότης Μαυρουδής ιδρύει το δισκογραφική ετικέτα «Corifeo» στην «Eros music», στο οποίο γίνεται καλλιτεχνικός διευθυντής και κάνει δισκογραφικές παραγωγές, με κορυφαία τον δίσκο “Master Class – Μισός αιώνας έλληνες κιθαριστές” (2005).
Ο Νότης Μαυρουδής ξεκίνησε να κάνει ραδιοφωνικές εκπομπές στις αρχές της δεκαετίας του ’80. Από το 1984 μέχρι το 1988 ήταν ραδιοφωνικος παραγωγός στο “Δεύτερο Πρόγραμμα” της ΕΡΑ, από το 1989 και μετά έχει συνεργαστεί με τους ραδιοφωνικούς σταθμούς “902 Αριστερά στα FM”, “Κανάλι 15”, “ΣΚΑΪ 100.3”, “Αθήνα 9.84”, και στο “Τρίτο Πρόγραμμα” της ΕΡΑ, με την εκπομπή “Τοπίο μυστικό”.
Από το 1982 μέχρι το 1986 έγινε εκδότης και διευθυντής του μοναδικού τότε περιοδικού για την κιθάρα, του TaR και οργάνωσε σημαντικές συναυλίες με κιθαριστές παγκόσμιας φήμης. Από τον Οκτώβριο του 2006 και σε συνεργασία με τον στενό του φίλο κιθαριστή-συνθέτη Κώστα Γρηγορέα, το TaR επαναλειτουργεί ως “διαδικτυακό περιοδικό με αφορμή την κιθάρα”, καλύπτοντας πλέον τον ευρύτερο χώρο της ελληνικής ποιοτικής μουσικής. Ο Νότης Μαυρουδής συμμετέχει σε αυτή την νεότερη μορφή πάλι ως διευθυντής, αλλά και ως τακτικός αρθρογράφος.
Ο Νότης Μαυρουδής υπήρξε επίσης αρθρογράφος στις εφημερίδες “Τα Νέα”, “24 ώρες”, “Ριζοσπάστης”, “Ελευθεροτυπία”, “Πρώτη”, “Δέντρο”, “Γράμματα και Τέχνες”, “Αντί”, “Σχολιαστής”, “Έθνος” και “ΦΛΥΑρία του Χαλανδρίου”.
Τον Φεβρουάριο του 2008 κυκλοφόρησε το βιβλίο “Ηχολογήματα” που περιλαμβάνει άρθρα του Νότη Μαυρουδή από τις παραπάνω εφημερίδες, αποσπάσματα από τις εκπομπές του, απόψεις, συνεντεύξεις κ.ά.
Στις Ευρωεκλογές του 2009 ο Νότης Μαυρουδής κατέβηκε υποψήφιος με τους Οικολόγους Πράσινους.
Το 2010 συμμετείχε στην ίδρυση του κόμματος της Δημοκρατικής Αριστεράς, της οποίας εκλέχθηκε μέλος της Πανελλαδικής Πολιτικής Επιτροπής.