Ο προμαχώνας Βηθλεέμ πήρε το όνομά του από τη μικρή εκκλησία της Παναγίας της Βηθλεέμ που βρισκόταν κοντά.
Έχει την τυπική διαμόρφωση και των άλλων προμαχώνων του Χάνδακα: δύο ημικυκλικά τμήματα, δύο χαμηλές πλατείες στις οποίες οδηγούν δυο θολοσκεπείς στρατιωτικές πύλες. Η όψη της βόρειας πύλης προς την πόλη έχει αξιόλογη διαμόρφωση. Στις χαμηλές πλατείες υπάρχουν χτιστές κανονιοθυρίδες και στοές εξόδου προς την τάφρο.
Στο νότιο ημικυκλικό τμήμα έχει εντοιχιστεί ανάγλυφη πλάκα με το φτερωτό λιοντάρι του Αγίου Μάρκου, τα διάσημα των αξιωματούχων και τη χρονολογία 1575.
Κοντά στον προμαχώνα μέχρι τις αρχές του 20ου αι. σωζόταν μια πυριτιδαποθήκη που χρησίμευε για την αποθήκευση της πυρίτιδας. Είχε ορθογώνιο σχήμα με θολωτή επικάλυψη και η εξωτερική της επιφάνεια ήταν πυραμοειδής. Το πάχος της ήταν από 1,74 ως 2,10 μ. ώστε να αντέχει αποτελεσματικά στην κρουστική δύναμη των εχθρικών βλημάτων. Η μορφή της θύμιζε μικρό πύργο.
Σήμερα οι στρατιωτικές πύλες που οδηγούν στις κανονιοθυρίδες των χαμηλών πλατειών του προμαχώνα έχουν αναπαλαιωθεί. Στο ισόπεδο του προμαχώνα έχει διαμορφωθεί χώρος πρασίνου και περιπάτου με πολύ ωραία θέα. Στην τάφρο κάτω από τον προμαχώνα έχουν διαμορφωθεί παιδικές χαρές και χώροι πράσινου.