Џамија Хуса Медин-паше припада раном цариградском стилу османске архитектуре. Осмоугаони, плитко засведени михраб на јужној страни разликује ову грађевину од других сачуваних грађевина овог типа у Македонији. Овај облик михраба, познат од 14. века, био је под утицајем касновизантијске и ране османске архитектуре.
Џамија је једнокуполна грађевина квадратне основе, чистих пропорција од 9,1 м, покривена куполом и додатним отвореним тремом на четири стуба, покривеним са три мале ниске куполе.
У унутрашњем северном углу џамије налазио се махфил, који је служио за женску молитву. Једини сачувани део махфила су камене степенице изграђене унутар зида, које су водиле до галеријског дела, нивоа вишег од приземља. У јужном углу џамије налазе се трагови минбера. Унутрашње осветљење је решено кроз три реда прозора. Отвори прозора су направљени од обрађених камених блокова и засведени су.
Трем џамије има једноставан, пропорционалан облик, типичан за исламску архитектуру 16. века. Подржавају га четири венца мермерних стубова. Два унутрашња су од зеленкастог мермера и имају декоративне капителе, а спољашњи су од белог мермера са декоративним капителима у облику „турских троуглова“. Лукови који носе куполе направљени су наизменичном употребом црвених и белих камених блокова, стварајући упечатљив декоративни ефекат.
Овај систем декорације примењен је и изнад главног улаза, на северној страни зграде, као и на прозорима који се налазе са стране улаза, и типичан је за османске грађевине из прве половине 16. века.
Минарет на западној страни џамије је ортогоналан, изграђен од зеленог пешчара донетог из околине Штипа. Минарет је, према свом облику, највероватније недовршен – без шерефе и кулафа, а природна порозност зеленог пешчара један је од разлога његовог оштећења. У унутрашњост минарета уграђене су камене степенице.
Поред џамије, на западној страни, налази се осмоугаона гробница, покривена црепом. У њој је сахрањен шеик Мухјудин Руми (Баба). Гробница је неколико пута реновирана, тако да је њена оригиналност нарушена и не може се дефинисати њен аутентични изглед.
