Џамија у Новој Вароши саграђена је у времену од 1887. до 1894. године, на рушевинама старе џамије коју је почетком 16. века подигао Перван-бег. Зидана је од ломљеног камена. Првобитно је била прекривена шиндром, а затим, црепом. До Другог светског рата имала је дрвени минарет који је касније замењен оним од клесаног камена. Изнад улазних врата постављена је ливена плоча посвећена добротвору џамије Махмут-бегу Бајровићу, чувеном богаташу из Пљеваља. Џамија се налази у центру града.