Постоечката библиотека во Валандово е основана во 1945 година и прво била сместена во куќата на Ристо Стамков во самиот центар на градот. На почетокот, таа броела 850 наслови кои биле донирани од домашните библиотеки на граѓаните на општината. До 1956 година, градската библиотека во Валандово се викала Народна библиотека, а потоа го  добила сегашното име „Гоце Делчев“. Од 1955 до 1959 година библиотеката работела во куќата на Јован Јованов, а од 1959 до 1961 година во просториите на домот за стари лица, односно малиот ресторан „Анска Река“. Од 1961 до 1981 година била сместена во просториите на поранешното кафе „Балкан“. Од 1981 година, библиотеката „Гоце Делчев“ се наоѓа во просториите на културниот центар во Валандово.
Прв библиотекар бил Ристо Турунџиев. Кратко по него работеле Пандора Гетова и Ѓорѓи Стојчев.
Од 1951 година, Васил Каракамчев е назначен за одговорен библиотекар, кој работи до неговото пензионирање, во 1987 година, во овој период од 1981 година, како библиотекар започнува да работи и Марика Манчева, која работи до 2011 година. Денес одговорна библиотекарка е Љилијана Нанова која започнува да работи во 1997 година.
Библиотечниот фонд од основањето на библиотеката постојано растеше и во 1995 година изнесуваше 27.500 публикации, а до денес тој број се зголеми на фонд од 36.620 книги, кои се поделени на дел за возрасни што содржи 25.605 книги, оддел за книги за деца што содржи 11.023 книги и изворна збирка од 173 книги. Библиотеката е збогатена со книги од неколку капитални проекти на Владата на Република Северна Македонија, како што се проектот „Превод на 1000
стручни, научни книги и учебници“,