Ο Ιερός Ναός της Αγίας Παρασκευής, Πολιούχου της πόλης της Χαλκίδας, χρονολογείται στον 5ο αιώνα μ.χ. κτισμένος πιθανόν πάνω στα ερείπια αρχαίου ναού.
Η εκκλησία της Αγίας Παρασκευής, Πολιούχου της πόλης της Χαλκίδας, βρίσκεται στην συνοικία κάστρο (περιοχή που βρισκόταν εντός των ενετικών τειχών της Χαλκίδας) και κοντά στο λιμάνι της Χαλκίδας. Απέναντι ακριβώς από τον ναό σώζεται η Οικία του Ενετού Βαίλου, του Διοικητή δηλαδή της Χαλκίδας κατά τα χρόνια της Ενετοκρατίας.
Στην τοποθεσία στην οποία βρίσκονται οι σύγχρονες βάσεις της εκκλησίας προυπήρχε βυζαντινή εκκλησία χτισμένη στα τέλη του 5ου ή στις αρχές του 6ου αιώνα. Κατά την περίοδο μεταξύ της αρχικής ανέγερσής και της τροποποίησης της τον 13ο αιώνα, υπήρχαν πιθανώς και άλλες αλλαγές.
Η πρώτη βασιλική πιθανώς καταστράφηκε κατά τη διάρκεια της Φραγκοκρατίας τον 13ο αιώνα. Στην ανακατασκευή της έγιναν τροποποιήσεις και προσθήκες τόσο στην κάτοψη όσο και στην υπερκατασκευή.
Μερικές από τις κολώνες της βασιλικής διατηρήθηκαν στην θέση τους και ενσωματώθηκαν στο νέο κτίσμα.