Choć z dzisiejszej nazwy spichlerza wnioskować by można, że ów Feierstein był jego budowniczym, to tak naprawdę przyczynił się tylko rozbudowy, po której dziś nie ma śladu.
Spichlerz zbudowany został ok. roku 1615 (na miejscu wcześniejszego drewnianego), a jego pierwszym właścicielem był niezwykle zasłużony i zamożny Kazimierzanin - Krzysztof Przybyła. Stąd też niektóre publikacje używają nazwy Spichlerz Krzysztofa Przybyły. Prawdopodobnie prace budowlane prowadzone były pod nadzorem mistrza murarskiego Stanisława Mysłowskiego.
Przybyłowie i ich potomkowie byli właścicielami spichlerza przez blisko półtora wieku. Następni właściciele zmieniali się bardzo często. Byli nimi Michał Mniszech (arystokrata, minister króla Stanisława Poniatowskiego), Paulina z Mniszchów Jabłonowska, Adam Jaraczewski, Józef Krasiński i na koniec wspomniany już żydowski przedsiębiorca Mejer Wulf Feierstein. Ten ostatni w 1838 roku przebudował budynek dodając jedną kondygnację i zewnętrzne schody oraz adaptując wnętrze na garbarnię, czym zapewne przyczynił się do upamiętnienia go w dzisiejszej nazwie spichlerza.
Garbarnia Feiersteinów działała do początku II wojny światowej, podczas której budynek został uszkodzony. W czasie odbudowy prowadzonej pod kierownictwem konserwatora Karola Sicińskiego została przywrócona forma budynku sprzed zmian wprowadzonych przez Feiersteina.
Od lat pięćdziesiątych XX w. w budynku funkcjonował skup płodów rolnych, a po kolejnym remoncie w 1983 r. budynek został przejęty przez Muzeum Nadwiślańskie. Kolejny remont przywracający zdobienia na fasadach był wykonany w latach 1993-94.
Jak większość kazimierskich budynków, spichlerz został wybudowany z bloków miejscowego wapienia, w stylu zwanym renesansem lubelskim. W przyziemiu spichlerz posiadał dwie równoległe komory, do których wchodziło się przez krużganki pod przybudówką znajdującą się nad wejściem. Dwuspadowy wysoki dach od strony fasady zakończony murowanym, trójkątnym, trójkondygnacjowym szczytem ozdobionym w stylu północnego manieryzmu, z ozdobnymi spływami wolutowymi i obeliskowymi sterczynkami. W osi szczytu dwie płyciny - górna pierwotnie rokiem przebudowy 1838 obecnie nieczytelnym, dolna z hierogramem IHS. Naroża głównej bryły i przybudówki oraz otwory okienne zostały ozdobione sgraffitową imitacją boniowania.
W 2021 r. obiekt niedostępny, planowana jest adaptacja na cele muzealne. W ewidencji zabytków od 1981 r.