Η ίδρυση της μονής αναζητάται πολύ προ του 1169, εφόσον σε έγγραφο του έτους εκείνου σώζεται υπογραφή Κουτλουμουσιανού ηγουμένου ανάμεσα σε υπογραφές εκπροσώπων 28 αγιορειτικών μονών. Σύμφωνα με την επικρατέστερη εκδοχή, ο ιδρυτής της μονής, μοναχός Κάλλιστος, προερχόταν από την αυλή του Κουτλουμούς, γενάρχου της ομώνυμης Μικρασιατικής δυναστείας Σελτζουκιδών. Πρώτος ευεργέτης της μονής ήταν ο αυτοκράτορας Αλέξιος Α΄ Κομνηνός.
Η μονή έλαβε μέρος σε όλα τα πνευματικά κινήματα της Ανατολής, αλλά επίσης υπέμεινε πολλές δοκιμασίες: την αυτοκρατορική βία μετά την αντίθεση του Αγίου Όρους στην ψευδένωση με τους παπικούς Λατίνους στη Λυών (1274), τις επιδρομές των Καταλανών και Τούρκων πειρατών (14ος αι.), την Οθωμανική δουλεία (1424-1912), αλλά και φυσικές καταστροφές από σεισμούς και πυρκαϊές.
Τον καιρό του αυτοκράτορα Μιχαήλ Η΄, όταν στρατιωτικό απόσπασμα έφθασε στο Άγιον Όρος για να επιβάλει την ένωση με τον πάπα, την οποία είχε υπογράψει ο Έλληνας αυτοκράτορας στην Λυών, αρκετοί μοναχοί μαζί με τον ηγούμενο απαγχονίσθηκαν και τάφηκαν πίσω από το Καθολικό. Η αιματηρή αυτή ομολογία δεν έμεινε άμισθη. Το 1287 ο Πρώτος του Αγίου Όρους —την εποχή εκείνη πρόσωπο εκλεγμένο με διοικητικές αρμοδιότητες εφ’ όλου του Αγίου Όρους— παραχώρησε στο Κουτλουμούσι τη διαλυμένη τότε μονή του Σταυρονικήτα, ενώ το 1329 παραχωρήθηκε η μονή του Αναπαυσά. Οι προσαρτήσεις αυτές, μαζί με τη φιλοπρόοδο διάθεση και τους πνευματικούς αγώνες των πατέρων, οδήγησαν τη μονή σε αλματώδη ανάπτυξη.
Οι απαρχές των σχέσεων της μονής με τη Βλαχία τοποθετούνται στα μέσα του 14ου αιώνα. Λεπτομέρειες για τις σχέσεις αυτές αντλούμε κυρίως από τις τρεις διαθήκες του Χαρίτωνα, του πιο φημισμένου ηγουμένου της μονής, ο οποίος εκλέχθηκε και Πρώτος του Αγίου Όρους. Ο Χαρίτων από την Ίμβρο ανέλαβε τους οίακες της μονής λίγο πριν το 1362 και επέδειξε τεράστιο ζήλο τόσο για την αδελφότητα όσο και για το μοναστηριακό συγκρότημα ως νέος κτήτορας. Με παραστάσεις και ενέργειές του προσεταιρίζεται τους ηγεμόνες της Ουγγροβλαχίας, οι οποίοι αναλαμβάνουν τη χρηματοδότηση ενός φιλόδοξου προγράμματος ανοικοδόμησης τμημάτων του μοναστηριακού συγκροτήματος και προβαίνουν σε κτηματικές δωρεές. Πρώτοι αρωγοί ήλθαν ο Αλέξανδρος Μπασαράμπ και ο διάδοχός του Ιωάννης Βλάδισλαβ. Ο τελευταίος όμως ζήτησε με επιμονή από τον Ηγούμενο να καταργήσει το κοινοβιακό σύστημα και να επιβάλει στη μονή τον ιδιόρρυθμο βίο, που επιτρέπει ίδιον πρόγραμμα και ατομική ιδιοκτησία. Τούτο εξυπηρετούσε τους τότε άμοιρους μοναστικής παραδόσεως Βλάχους μοναχούς, οι οποίοι ζητούσαν να εγκαταβιώσουν εκεί, πλην όμως δεν φαίνονταν έτοιμοι να προσαρμοσθούν στις απαιτήσεις της κοινοβιακής ζωής. Ο Χαρίτων γράφει πως «η κοινοβιακή κατάσταση είναι ο επίγειος ουρανός και κλήρος των πατέρων» και διαμαρτύρεται για την «αήθη και ξένη των αληθών μοναχών βιωτή» των Βλάχων. Τελικώς, όμως, κατόπιν ισχυρών πιέσεων και μπροστά στο οικονομικό αδιέξοδο το Κουτλουμούσι «ὑπέκλινε τῆς κοινοβιακῆς ὁδοῦ καὶ ἐβάδισε τὴν τῶν ἑτέρων ἁγιορειτικῶν μονῶν», υπό τον όρο πάντως να αποσώζονται «τοῖς Ῥωμαίοις τὰ πρωτεῖα», δηλαδή να παραμείνει ελληνικό μοναστήρι. Αποτέλεσμα των σχέσεων αυτών ήταν η βαθιά επίδραση του ελληνικού στοιχείου στον πνευματικό βίο των παρίστριων επαρχιών. Δεν είναι τυχαίο το ότι ο Οικουμενικός Πατριάρχης άγιος Φιλόθεος Κόκκινος χειροτονεί το 1372 μητροπολίτη Ουγγροβλαχίας τον Χαρίτωνα, ο οποίος όμως δεν παραιτείται από την ηγουμενία στη μονή.
Τον 14ο αιώνα το Κουτλουμούσι δεν έπαψε να ταλαιπωρείται από ληστρικές επιδρομές των πειρατών. Στην κρίσιμη περίοδο φθάνει η βασιλική ενίσχυση στο πρόσωπο του Ανδρονίκου Β΄ Παλαιολόγου και λίγο αργότερα της Θεοδώρας Καντακουζηνής, με αντάλλαγμα να μνημονεύεται το όνομά της καθημερινά στη Θεία Λειτουργία και να ψάλλονται ετησίως ευχές για την ανάπαυση της ψυχής της. Το 1393 και 1395 ο Οικουμενικός Πατριάρχης Αντώνιος διακηρύσσει το Κουτλουμούσι και επισήμως Πατριαρχική Μονή, επικυρώνοντας την ανεξαρτησία της από κάθε πολιτική ή τοπική εκκλησιαστική αρχή, συμπεριλαμβανομένων των πατριαρχικών εξάρχων. Η αυτοδεσποτεία αυτή εξασφαλιζόταν και από τα αυτοκρατορικά χρυσόβουλλα, χάρις στα οποία οι μονές αποκαλούνται βασιλικές.
Το 1497 το Κουτλουμούσι διέρχεται δια πυρός, για να αναστηθεί πάλι μέσα από τις στάχτες του. Στους αιώνες που ακολουθούν συνεχίζεται η παραχώρηση εκτεταμένων γαιών και μετοχίων από τους Βλάχους ηγεμόνες, ενώ αναλαμβάνεται ο έσωθεν και έξωθεν εξωραϊσμός του σε ένα μεγάλο ανακαινιστικό πρόγραμμα. Το 1508 οικοδομείται ο αμυντικός πύργος από τον Ράντου τον Μέγα, ενώ μια σημαντική περίοδος ως προς τις σχέσεις της μονής με τη Βλαχία είναι επίσης εκείνη του Νεαγκόε Μπασαράμπ (1512-1521), ο οποίος επονόμασε τη μονή «μεγίστη Λαύρα της Ρωμανικής Χώρας».
Δυσβάστακτες όμως ήσαν οι συνέπειες της πτώσεως της Αυτοκρατορίας: οικονομική κρίση λόγω επαχθούς φορολογίας και αποσπάσεως μοναστηριακών κτημάτων, και μείωση του αριθμού των μοναχών. Ευτυχώς εν καιρώ οι μονές πέτυχαν να εξαρτώνται όλες οι πολιτικές υποθέσεις τους απ’ ευθείας από τον Σουλτάνο. Από το 1574 η μονή του Κουτλουμουσίου κατέλαβε την έκτη θέση στην τιμητική ιεραρχία των μονών του Άθω. Τον 17ο και 18ο αιώνα για τη μονή φροντίζουν μόνον ευσεβείς Έλληνες, ενώ ιερομόναχοι αποστέλλονται προς εξυπηρέτηση των ανθηρών Ελληνικών κοινοτήτων της κεντρικής Ευρώπης. H εκπνοή του αιώνα θα αναδείξει τη δόξα της νεώτερης ιστορίας του Κουτλουμουσίου, τον Ίμβριο λόγιο Βαρθολομαίο, διδάσκαλο του Γένους και διορθωτή των λειτουργικών βιβλίων.
Το 1856 με ομόφωνη αίτηση των πατέρων προς τον Οικουμενικό Πατριάρχη η μονή επανέρχεται στην αρχαία κοινοβιακή τάξη μετά από ιδιόρρυθμο βίο πέντε αιώνων.
Το 1863, ο Έλληνας εκ μητρός ηγεμόνας της Βλαχίας Αλέξανδρος Ιωάννης Α΄ ή Κούζα μετά από σειρά εχθροπραξιών προς τις Ορθόδοξες Εκκλησίες κατάσχει τα μετόχια όλων των Αθωνικών μοναστηριών, συμπεριλαμβανομένων αυτών της μονής Κουτλουμουσίου. Το 1870 επίσης πυρκαϊά καταστρέφει το μεγαλύτερο τμήμα του μοναστηριού. Ο ιερομόναχος Μελέτιος, διακεκριμένος για την αρετή και τα υψηλά διοικητικά του προσόντα, φθάνει με την ευλογία του Πατριαρχείου μέχρι τη Ρωσία, την Ευρώπη και την Αγγλία με μοναστηριακά γράμματα, για να διενεργήσει εράνους, έχοντας μαζί του το Τίμιο Ξύλο. Ανακατασκευάζει έτσι τη βόρεια πτέρυγα αλλά η κοίμησή του διακόπτει το ευρύτερο ανακαινιστικό του σχέδιο.
Μετά το Β΄ Παγκόσμιο πόλεμο το Κουτλουμούσι παραδόθηκε σε λειψανδρία. Η φθορά του χρόνου, μαζί με την απώλεια του μεγαλύτερου μέρους της περιουσίας του, έθεσαν σε κίνδυνο τη βιωσιμότητά του. Το 1980 αποτεφρώθηκε η ανατολική πτέρυγα, ενώ ραγδαίες βροχές προκάλεσαν κατολισθήσεις και ρηγματώσεις. Την ίδια εποχή όμως, με την προσέλευση νέων μοναχών άρχισε για τη μονή μια νέα περίοδος αύξησης και άνθισης. Στους εξαρτηματικούς αδελφούς της μονής ανήκε και ο γέρων Παΐσιος (Εζνεπίδης), που ασκήτεψε τα δεκαπέντε τελευταία χρόνια της ζωής του στο Κελλί Παναγούδα και η φήμη της αγιότητάς του απλώθηκε σε όλο τον κόσμο.
Η μονή πανηγυρίζει στις 6 Αυγούστου. Υπάρχει επίσης αρχαίο έθιμο να υποδέχεται την εικόνα του Άξιον Εστί κατά τη λιτανεία της τη Δευτέρα της Διακαινησίμου και να αποστέλλει εφημέριο και ψάλτες στο Πρωτάτο για την τέλεση του Εσπερινού μετά το πέρας της λιτανείας. Την επόμενη ημέρα τελείται η λιτανεία της Κουτλουμουσιανής εικόνας, της Φοβεράς Προστασίας, την οποία υποδέχονται πανηγυρικά οι Καρυές και ο ναός του Πρωτάτου.