Εντός της παραδοσιακής συνοικίας Βαρόσι της Έδεσσας, βρίσκεται ο ναός των Αποστόλων Πέτρου και Παύλου, ενταγμένος στον παλαιό πολεοδομικό ιστό και τοποθετημένος δίπλα στο φρύδι του βράχου της πόλης.

Το μνημείο, στη σημερινή του μορφή, είναι τρίκλιτη βασιλική μικρών διαστάσεων, της εποχής της Τουρκοκρατίας. Η αρχική, όμως, φάση οικοδόμησής του ανάγεται στα βυζαντινά χρόνια. Από αυτή διατηρείται τμήμα της τοξοστοιχίας, των τοίχων του φωταγωγού και οι ανατολικοί πεσσοί. Στη δυτική πλευρά βρίσκεται εντοιχισμένη μαρμάρινη πλάκα που αναγράφει το έτος 1864, χρονολογία, κατά την οποία ο ναός δέχθηκε επισκευές μεγάλης κλίμακας, που αλλοίωσαν τον αρχικό χαρακτήρα του και του προσέδωσαν τη σημερινή του μορφή.

Εσωτερικά, στους τοίχους επάνω από την κιονοστοιχία διασώζεται αποσπασματικά τοιχογραφικός διάκοσμος, που χρονολογείται στην περίοδο 1370-1385. Πρόκειται για έργο υψηλής ποιότητας, που σχετίζεται με το καλλιτεχνικό κέντρο της Θεσσαλονίκης και φανερώνει ότι ο δημιουργός του ήταν γνώστης των κυρίαρχων ζωγραφικών ρευμάτων της εποχής.

Οι κίονες και τα κιονόκρανα που στηρίζουν τα τόξα ανήκουν σε παλαιότερα μνημεία και εδώ χρησιμοποιούνται σε δεύτερη φάση. Ιδιαιτέρως αξιόλογο είναι το νοτιοανατολικό κιονόκρανο, που στις τέσσερις γωνίες φέρει ανάγλυφες παραστάσεις αετών με ανοικτά φτερά. Χρονολογείται στις αρχές του 11ου αι.