Po zniszczeniach bułgarskich Konstanca stała się w tym czasie niewielką osadą.

W średniowieczu Constantiniana pojawiła się ponownie pod nazwą Constanza jako jeden z rynków handlowych włoskiego miasta Genua w basenie Morza Czarnego. Genueńscy kupcy i armatorzy osiedlali się na półwyspie i wykorzystali rzymskie ruiny do budowy nowych fortyfikacji wzdłuż obecnej ulicy Sulmona. Do dziś zachowały się fundamenty z tamtych czasów, na którym później zbudowano tzw. „Latarnię Genuańską”. Po rozpadzie Drugiego Państwa Bułgarskiego nastąpił na początku XV wieku okres włączenia Konstancy i Dobrudży do rumuńskiego państwa hospodara wołoskiego Mirczy Starego.

Po 1419 roku Dobrudża wraz z Konstancą weszły w zależności od Imperium Osmańskiego, które nadało miastu nazwę Küstence. Znaczenie miasta zmalało, gdyż Turcy zerwali stosunki handlowe z morskimi republikami z terenu Italii. W XVII wieku osada była atakowana przez Kozaków zaporoskich. W XIX w. sułtan zlecił budowę portu, który cieszył się rosnącym rozwojem i znaczeniem. W 1855 roku, gdy floty angielska i francuska płynąc na Krym na wojnę przeciwko Rosji, zatrzymywały się w porcie, aby nabrać zapasów. Konstanca, jak opisał dr Camille Allard, rozciągała się wówczas jedynie na półwyspie, na południowy wschód od obecnej ulicy Negru-Vodă.