Η αρχική γέφυρα Ζέζελι (μήκους 377 μέτρων) χτίστηκε από το 1957 έως το 1961 ως αψιδωτή γέφυρα. Η γέφυρα σχεδιάστηκε από τον εξέχοντα γιουγκοσλάβικο πολιτικό μηχανικό Μπράνκο Ζέζελι και κατασκευάστηκε από την Mostogradnja.[1][2] Συνέδεε την αστική περιοχή του Νόβι Σαντ και το Πετροβαραντίν. Κατά τη διάρκεια της ύπαρξής της, υπηρέτησε ως μέρος διεθνούς σιδηροδρομικής γραμμής και ως διαδρομή μεταφοράς μέσω του Νόβι Σαντ.[2]
Κατά τη διάρκεια των νατοϊκών βομβαρδισμών της Γιουγκοσλαβίας, η γέφυρα βομβαρδίστηκε 12 φορές. Στις 23 Απριλίου 1999, τελικά κατεδαφίστηκε, με αποτέλεσμα το κόψιμο των σιδηροδρομικών μεταφορών μεταξύ Βελιγραδίου και Σουμπότιτσα, δηλαδή της Σερβίας και της Ουγγαρίας.[3] Κατά την διάρκεια των βομβαρδισμών, οι τρεις μεγάλες γέφυρες επί του Δούναβη στο Νόβι Σαντ (Γέφυρα Ζέζελι, Γέφυρα Βαραντίν και Γέφυρα Ελευθερίας) κατεδαφίστηκαν ολοκληρωτικά.
Το 2000 κατασκευάστηκε μια προσωρινή Οδική-Σιδηροδρομική Γέφυρα κοντά στη γέφυρα Ζέζελι, η οποία κατασκευάστηκε για να αντικαταστήσει τη γέφυρα Ζέζελι μέχρι να κατασκευαστεί η νέα. Με τα χρόνια, η κατασκευή της νέας γέφυρας Ζέζελι αναβλήθηκε αρκετές φορές.[4]
Τον Απρίλιο του 2012 οι εργασίες κατασκευής της νέας γέφυρας στον ίδιο χώρο ξεκίνησαν επίσημα.[5] Ο κύριος σχεδιαστής της νέας γέφυρας ήταν ο Αλεξάνταρ Μπόγιοβιτς, ενώ ο συμβασιούχος ήταν μια διεθνής κοινοπραξία, η JV Azvi - Taddei – Horta Coslada.[6] Η νέα γέφυρα είναι οπτικά σχεδόν πανομοιότυπη με την κατεδαφισμένη γέφυρα, εκτός από το ότι οι αψίδες είναι κατασκευασμένες από χάλυβα και όχι προεντεταμένο σκυρόδεμα.[7] Επίσης, η γέφυρα αποτελείται από δύο αψίδες μήκους 177 μέτρων και ύψους 34 μέτρων, ενώ η μεγαλύτερη αψίδα έχει μήκος 219 μέτρων και ύψος 42 μέτρων.[7]
Τον Οκτώβριο του 2017, οι αψίδες της γέφυρας Ζέζελι συνδέθηκαν μετά από πέντε χρόνια κατασκευής και δεκαοχτώ χρόνια μετά την κατεδάφιση της προηγούμενης γέφυρας.[8] Τον Οκτώβριο του 2017, το κόστος κατασκευής ήταν 51.71 εκατομμύρια ευρώ.[8] Τον Απρίλιο του 2018 η γέφυρα ολοκληρώθηκε και δημιουργήθηκαν τακτικές σιδηροδρομικές μεταφορές.[9] Οι οδικές μεταφορές αναμένονται να ολοκληρωθούν το 2018.[6]