Хуса Медин-пашината џамија припаѓа на раноцариградскиот стил на османлиската архитектура. Октогоналниот, плитко засведен михраб од јужната страна ја издвојува оваа градба од останатите сочувани објекти од овој тип во Македонија. Ваквата форма на михраб, позната уште од XIV век, е добиена под влијание на доцновизантиската и раноотомaнската архитектура.
Џамијата по својата форма претставува еднокуполна градба со квадратна основа, со чисти пропорции од 9,1 м, покриена со купола и придодаден отворен трем на четири столба, покриен со три мали ниски куполи.
Во внатрешниот северен агол на џамијата се наоѓал махвил, кој служел за молитва на жените. Единствен сочуван дел од махвилот се камените степеници изведени во внатрешноста на ѕидот, кои воделе до галерискиот дел, на едно ниво повисоко од приземјето. На јужниот агол на џамијата постојат траги од минбарот. Осветлувањето на ентериерот е решено преку три реда прозорци. Прозорските отвори се од обработени камени блокови и се засведени.
Тремот на џамијата е со едноставна, пропорционална форма, типична за исламската архитектура од XVI век. Прифатен е со четири круни мермерни столба. Двата внатрешни се од зеленкаст мермер и имаат декоративни капители, а надворешните се од бел мермер со декоративни капители во форма на „турски триаголници“. Арките што ги држат куполите се изведени со алтернација на наизменична употреба на црвени и бели камени блокови, создавајќи впечатлива декоративност.
Овој систем на декорација е применет и над главниот влез, на северната страна на објектот, како и на прозорите што се наоѓаат од страните на влезот, и е типичен за османлиските градби од првата половина на XVI век.
Минaрето од западната страна на џамијата е ортогонално, градено од зелен песочник донесен од околината на Штип. Минарето, според својот облик, најверојатно е недовршено – без шерефе и кулаф, а природната порозност на зелениот песочник е една од причините за неговото оштетување. Во внатрешноста на минарето се вградени камени степеници.
Веднаш до џамијата, од западната страна, се наоѓа октогонално турбе, покриено со ќерамида. Во него е погребан шеихот Мухјудин Руми (Баба). Турбето е повеќепати обновувано, така што неговата оригиналност е нарушена и не може да се дефинира автентичниот изглед.
