Музејот во Штип е отворен со одлука на Народниот одбор на градот Штип на 10.5.1950 година. Првата поставка на Музејот е поставена во Хуса – Медин пашината џамија и имала етнолошки карактер. На 11.10.1956 година Музејот е преместен во ново-адаптирана зграда од староградска архитектура, позната како куќата на Арсови (браката Тошо и Љупчо, народни херои).
Во 1964 година беше отворена постојана изложбена поставка на современо македонско сликарство во уметничката галерија Безистен, која претставува дел од Музејот. Во 1972 година, на иницијатива на Коста Балабанов, во црквата од 19 век – Устание на пресвета Богородица во Ново Село е отворена постојана поставка на икони.
