Κτίστηκε από το στρατηγό του Ιουστινιανού Βελισσάριο το 532 μ.Χ., όπως αναγράφεται και από επιγραφή που σώζεται έως και σήμερα, ώστε να εξιλεωθεί από την σφαγή κατά την περίφημη "Στάση του Νίκα" στην Κωνσταντινούπολη.
Στο μέσο του Μοναστηριού είναι κτισμένος ο ναός την Παναγίας όπου και εκεί βρίσκεται η θαυματουργή εικόνα της Παναγίας και είναι αξιοσημείωτο να αναφερθεί ότι αίσθηση προκαλεί η εικόνα τούτη διότι όποια θέση κι αν κοιτάξει ο προσκυνητής την εικόνα τα μάτια Της είναι στραμμένα προς αυτόν.
Το όνομα του μοναστηριού αρχικά ήταν Παναγία η Λιθοστρωτιώτισσα λόγω του ότι είναι κτισμένο πάνω σε βράχο.
Το όνομα "Μακελλαριά" το απέκτησε λόγω του μακελειού που έγινε όταν οι Τούρκοι πήγαν να το κατακτήσουν.
Η παράδοση θέλει τους Τούρκους να απωθούνται από τους μοναχούς και τους υποτακτικούς που βρισκόταν εκεί και το Ηγούμενο της Μονής να κάνει συμφωνία με τον στρατηγό των Τούρκων, ότι εάν σπάσει το καντήλι που θα πετάξουν στο βράχο, τότε θα παραδοθούν, αν όμως δεν σπάσει θα φύγουν χωρίς να κάψουν την Μονή. Έτσι κι έγινε, πέταξε ο Ηγούμενος το καντήλι της Παναγίας στο βράχο, κατέβηκαν δύο Τούρκοι στρατιώτες και βρήκαν το καντήλι να κρέμεται από ένα κλαδί ενός δένδρου και μάλιστα με την φλόγα του καντηλιού να καίει ακόμα. Το ανέβασαν στον στρατηγό τους και εκείνος με τη σειρά του τήρησε την συμφωνία.
Αργότερα όμως έγινε μακελειό μεταξύ των Τούρκων επειδή δεν έκαψαν την Μονή, μιας και ο σκοπός που πήγαν εκεί ήταν αυτός.
Ο πολυτιμότερος θησαυρός είναι η θαυματουργή εικόνα της Παναγίας & το κιούπι με το θαυματουργό λάδι που βρέθηκε μέσα στο βράχο όταν ξανακτίστηκε το μοναστήρι μετά την καταστροφή που υπέστη από τους Τούρκους το 1458, το οποίο σώζεται έως και σήμερα.
Κάθε χρόνο στην εορτή της Παναγίας στις 15 Αυγούστου, πολλοί πιστοί από τα γύρω χωριά έχουν έθιμο η τάμα, να πηγαίνουν με τα πόδια στη Ιερά Μονή για να προσκυνήσουν και να ακούσουν τις ψαλμωδίες. Αποστάσεις οι οποίες μερικές φορές ξεπερνούν τα 15 χιλιόμετρα.Τρεις και τέσσερις ώρες δρόμο μέχρι να φθάσουν. Παρέες η μοναχικοί οι προσκυνητές διαβαίνουν μέσα από το δάσος της Κάνισκας τον ατέλειωτο χωματόδρομο με προορισμό το μοναστήρι.