Поселение на месте современного города известно с середины XVII века. В 1701 году упоминается слобода Зыбкая, основанная старообрядцами. Название от древнерусского "зыбь" — "зыбкое место, топь": как утверждают краеведы, слобода была основана на месте, затопляемом в паводки — после ее переноса на новое место название сохранилось.

В XIX - начале XX века Новозыбков — крупнейший центр производства спичек (первая фабрика была построена в 1864 году).

Основные достопримечательности Новозыбкова: Никольско-Рождественская церковь (XVIII век, перестроена в 1818 году), Спасо-Преображенский собор (1911-14), Троицкая церковь (начало XX века, перестроена под школьные мастерские в советское время, восстановлена в 1990-х годах), Собор Чуда Михаила Архангела (1867-98), Банк (1902), Дом Певзнера (1884), Дом Абросимова (1896), Дом Осипова (1898), Дом Волкова (1904), Церковь Рождества Богородицы в Людково (XVIII век, во второй половине ХХ века службы прекращены, частично разрушена местными жителями, перестраивается), Женская гимназия (1880).