Основањето на Крива Паланка датира од првата половина на XVII век, поточно во 1633 година, во времето на турската империја, кое нешто ни го потврдува еден историски документ – споменик, односно мермерна плоча, која што во тоа време се наоѓала на влезната порта на кривопаланечката тврдина, а денеска се наоѓа како музејски предмет во Музејот на Македонија.
Кривопаланечкото утврдување, кое било направено во тоа време, го следело текот на Крива Река, и десниот брег на Дурачка река, при што тврдината била обиколена од две страни со коритата на двете кривопаланечки реки.