Nyborg Bibliotek består af to skarptskårne, en-etagers røde teglstenslænger liggende drejet i forhold til hinanden, således at de følger voldgravenes stensætninger og forbundne i den søndre ende af et indgangsparti af glas.

Bygningerne blev opført 1938-39, fik året efter tildelt Eckersberg Medaillen og blev fredet i 1986 som det første bygningsværk her i landet, som blev fredet, mens en af arkitekterne, der tegnede det, stadig var levende.