Джамията „Хуса Медин паша“ принадлежи към ранния константинополски стил на османската архитектура. Осмоъгълният, плитко засводен михраб от южната страна отличава тази сграда от другите запазени сгради от този тип в Македония. Тази форма на михраб, позната от 14-ти век, е повлияна от късновизантийската и ранноосманската архитектура.
Джамията е еднокуполна сграда с квадратна основа, с изчистени пропорции от 9,1 м, покрита с купол и добавен открит портик на четири стълба, покрит с три малки ниски купола.
Във вътрешния северен ъгъл на джамията е имало махфил, който е служил за женска молитва. Единствената запазена част от махфила са каменните стъпала, построени във вътрешността на стената, които са водили към галерийната част, едно ниво по-високо от партера. В южния ъгъл на джамията има следи от минбара. Вътрешното осветление е решено чрез три реда прозорци. Отворите за прозорци са изработени от обработени каменни блокове и са сводести.
Верандата на джамията има семпла, пропорционална форма, типична за ислямската архитектура от XVI век. Тя се поддържа от четири корони от мраморни колони. Двете вътрешни са от зеленикав мрамор и имат декоративни капители, а външните са от бял мрамор с декоративни капители във формата на „турски триъгълници“. Арките, които поддържат куполите, са направени чрез редуване на червени и бели каменни блокове, създавайки поразителен декоративен ефект.
Тази система на декорация е приложена и над главния вход, от северната страна на сградата, както и върху прозорците, разположени отстрани на входа, и е типична за османските сгради от първата половина на XVI век.
Минарето от западната страна на джамията е ортогонално, построено от зелен пясъчник, донесен от района на Щип. Минарето, според формата си, най-вероятно е недовършено – без шерефе и кулаф, а естествената порьозност на зеления пясъчник е една от причините за повредата му. Във вътрешността на минарето са вградени каменни стъпала.
До джамията, от западната страна, се намира осмоъгълна гробница, покрита с керемиди. В нея е погребан шейх Мухюдин Руми (Баба). Гробницата е реновирана няколко пъти, така че нейната оригиналност е нарушена и автентичният ѝ вид не може да бъде определен.
