Bedesten ən qədim tarixində Bizans bazilikası olmuşdur və onun fraqmentləri mövcud binada hələ də qorunub saxlanılır. Kiprdəki Afendrika və Ayios-Filon kilsələri ilə bənzər struktur xüsusiyyətləri daşıyan bu qalıqlar ehtimal ki, altıncı əsrə aiddir. Bu qalıqlar şəhərdəki ilk Müqəddəs Sofiya kafedralinin yeri olaraq qəbul edilmişdir.

Daha sonra Kipr krallarının hakimiyyətinə keçən binanın sonrakı tarixi yaxşı sənədləşdirilməmişdir. Lakin Kamil Enlart da daxil olmaqla bəzi tarixçilər Əkkanın süqutundan sonra, XII əsrin sonlarında Tomas Beketin davamçıları olan ingilis rahiblərinin bu ərazidə Müqəddəs Nikolaya həsr edilmiş yeni bir Latın kilsəsi qurduqlarını qeyd etmişdir. Lakin bu mənbələr Müqəddəs Tomas cəngavərlərinin Latın şərq tarixində az rol oynadığı nəzərə alınaraq ümumiyyətlə qəbul edilmir. Kilsə bir neçə dəfə genişləndirilmiş və on dördüncü və on beşinci əsrlərdə yenidən qurulsa da, köhnə Bizans apsisi saxlanılmışdır.

Adada Venesiya hakimiyyəti dövründə Bedesten, Pravoslav kilsəsinə məxsus metropoliten yepiskop binası olaraq istifadə edilmiş və Məryəmə həsr edilmişdir. Bina bu dövrdə onun ən diqqətəlayiq hissəsini - şimal fasadını inşa etmiş venesiyalarının səlahiyyətində idi. Tikilinin himayədarları isə əsas girişin üstündə oyulmuş gerblər tərəfindən qismən sənədləşdirilmiş nəcib Kiprli ailələr idi. Məhz bu dövrdə Bizans dövrünə aid orijinalını əvəz edən günbəz və böyük mərkəzi apsis inşa edilmişdir.

1573-cü ildə, Osmanlının Kipri fəth etməsindən bir neçə il sonra bina Osmanlı rəhbərliyi tərəfindən bedesten (örtülü bazar) olaraq istifadə edilməyə başlanıldı. Tikili daha sonra qida üçün bir bazar olaraq istifadə edildi və 1760-cı illərdə türk, yunan və erməni tacirləri üçün bir qida ticarəti mərkəzi oldu. Bina 1873-cü ilə qədər dövlət məmurları tərəfindən Kitreyadan gətirilmiş məhdud şəkildə satıldığı un deposuan çevrildi. Tikili həmçinin 1870-ci illərdə buğda anbarı və 1930-cu illərdə ümumi bir anbar kimi də istifadə edilmişdir.

1880-ci illərdə, İngilis müstəmləkə hakimiyyətinin ilk illərində Herberd Kitçener və Kiprdəki digər məşhur ingilislər yenidən Müqəddəs Nikolay kilsəsi olaraq istifadə etmək üçün binanı almaq və ya icarəyə götürmək istədilər. Lakin məsciddən 100 metr məsafədə yerləşən bir vəqf mülkünün satıla bilmədiyi və başqa bir dinin ziyarətgahı açıla bilmədiyi üçün buna icazə verilmədi. İngilislər hava və zəlzələ səbəbindən zədələnmiş binada bir qədər bərpa işləri həyata keçirsə də, bu, orijinal memarlığa uyğun olmadığı üçün uğursuzluqla nəticələndi. 1932-ci ildə şəhərdə Bandabulya adlı yeni bələdiyyə bazarının açılması ilə bina istifadəsiz hala gəldi. 1930-cu illərdə bina anbar olarq istifadə edildi və 1935-ci ildə binaya Ömerge məscidindən bəzi orta əsr qəbir daşları gətirildi. Bu məzar daşları bir müddət Osmanlı dövrünün bəzəkli tavanı ilə birlikdə otaqda nümayiş olnumşdur.

Nikosiya bedesteni üslub baxımından Osmanlı İmperiyasındakı digər bedestenlərdən olduqca fərqlidir. Tikili əsasən Bizans və Qotik memarlığın qarışığından ibarətdir. Bedestenə həmçinin ikincisi Kipor krallları tərəfindən əlavə olnumşdur və intibah, Venesiya və bi qədər də ispan memarlıq üslublarının elementlərini özündə birləşdirir. Binada bizans üslubuna aid xaç şəkilli bir quruluş üslubundan və tərtibatından istifadə ediilmiş, eyni zamanda qoik üslubuna aid yüksək tavanlı bir nef inşa edilmişdir. Cənub nefi Bizans kilsəsinin qalığıdır və orta hissəsi binanın ən qədim hissəsi hesap olunur. Şimaldakı nefin xarici fasadı isə binada ən çox bəzədilmiş hissədir. Bu fasad Səlimiyə məscidinin ön tağları arasındadır və girişin yerləşdiyi tərəfdir. Giriş daha sonra italyan renesans memarlığının elementləri əlavə edilmiş və Müqəddəs Nikolas heykəlciyi ilə bəzədilmiş qotik üslublu qapıdan ibarətdir. Girişin hər iki tərəfində gerblər işlənilib. Bu fasadda çox sayda heyvan heykəlciyi və qarqoyl mövcuddur.

Binada 2004-cü ilin iyunu və 2009-cu il arasında BMT-nin İnkişaf proqramı çərçivəsində Avropa Birliyi və Evkaf idarəsi tərəfindən maliyyələşdirilən yeniləmə layihəsi həyata keçirilmişdir. Bərpa zamanı binanın divarları təmizlənmiş və sütunlar ənənəvi tikinti materialları və texnikadan istifadə edilərək möhkəmləndirilmişdir. Bərpa işləri başa çatdıqdan sonra bina mədəniyyət mərkəzi olaraq yenidən açışmışdır.

Binanın ev sahibliyi etdiyi fəaliyyətlər arasında həftəlik sufi rəqs şouları var. Binada həmçinin, Lefkoşa Divarlı Şəhər Caz Festivalı da keçirilir.