Tütünsüz Camii eski Üsküp'ün doğusunda Gazi Baba'nın altında yer almaktadır. Onun hakkında yeterli bilgi yok çünkü camiye girişin üzerindeki yazıt korunmamıştır, vakıfnamesi de korunmamıştır. Caminin 17. yüzyılda inşa edildiği söylenir, ancak inşaatçı bilinmemektedir, bu yüzden orijinal adı bilinmemektedir. Muhtemelen caminin yanında inşa edilen Tütünsüz medresesi'nin varlığına dair bilgi vardır.
Tütünsüz Camii, revak pahasına dua alanının arttığı 1963 depreminden bu yana yapılan müdahalelerle desteklenen oldukça değiştirilmiş bir görünümde korunmuştur. Minare tamamen korunmuştur. Alt kısım taş ve tuğladan ve daha sonra sadece işlenmiş taştan yapılmıştır. Minareye, şerefe girişine ve en tepenin altına uygulanan çeşitli dekoratif elemanların uygulanmasından görülen estetik görünüme büyük önem verilmiştir.
Avlu düz ve düzenli, ancak eski mezarlıktan mezar taşları yok. Ancak caminin dışında, çevredeki evlerin önünde, Tütünsüz Camii mezarlığından kaynaklanan birkaç kırık niş ve mermer levha vardır.
Bu caminin bilindiği " Tütünsüz " adı ile ilgili olarak, şunlar anlatılır:
Zamanında bir bakkal varmış. Bu bakkalı iki kardeş uzun yıllar birlikte çalıştırmışlar.Bu iki kardeş daima birbirlerini kollamış, geçen yıllar boyunca çok iyi geçinerek birbirlerini hiç kırmamışlar. Aralarında hiç bir tartışma dahi olmaksızın yaşayıp gidiyorlarmış. Herkes gibi bir gün bu kardeşler evlenmişler, çoluk çocuk sahibi olmuşlar. Zamanla çocukları büyümüş birer yetişkin olmuşlar.
Hepsine yeten dükkan geliri artık yetmez olmuş. Bir şeyler yapıp gelirlerini artırmak için ne yapacaklarını düşünmeye başlamışlar. Küçük kardeş,"Var mısın ağabey, ayrılalım. Sen yaşlısın, yerinden kıpırdama. Ben gidip uygun bir yere bir dükkan açayım." demiş. Böylece küçük kardeş uygun bir yer bularak dükkanını açmış.
Ağabeyi kasadaki paranın, raflardaki malların yarısını kardeşine vermiş. Helalleşip kucaklaşmışlar Küçük kardeş tam yola koyulacakkenağabeyi "Durasın bre" demiş, "Şunu da alasın!" Küçük kardeş bakmış, içi para dolu koca bir kese.
-"Abi bu ne?"
-"Tütün parası. Bilirsin ben cigara içerim sense içmaysın.Canım cigara istediğinde raftan bir paket alıp yakardım. Bunca yıldır kasaya para atmak hiç aklıma gelmedi."
-"Eee, kendi dükkanına ödeme yapacak değildin ya"
-"Kaç yıl ama... Günde bir paket olsa yılda 365, 10 yıla 3650 paket. Otuz yılda on binden fazla... Az buz bir şey değil. İşte bu oyılların cigara parası."
-"Ya abi, lafı mı olur. Zaten helalleştik ya."
-"Al şunu. Yoksa ben sürekli husuzsuz olurum."
-"Almam."
-"Al diyorum sana.
-Kesinlikle alma. Elimi bile sürmem o paraya."
--"Abe büyük sözü dinle. Al şu parayı."
-"Abi be! Bak ne geldi aklıma!"
-"Ne geldi? Söyle bakam!"
-"Bu paraya seninde benimde ihtiyacımız yok.Bir cami yaptıralım. Sevabı ölmüşlerimizin ruhuna gitsin. Ne dersin?"
Böylece düşündüklerini gerçekleştirerek o parayla Tütünsüz Camiini yaptırmışlar.
Kardeşlerin bu hayrı 1963 yılındaki Üsküp depreminde de zarar görmemiş?