A Középkori Kőtár a múzeum gyűjteményének egyik legkorábbi része. Gyűjtését már a 19. század második felében megkezdték a Mátyás-templom és a királyi palota újjáépítésekor, amely darabok ma is a magját képezik a kőtárnak. Az ekkor még rendszertelen kutatás és gyűjtés következtében a gyűjtemény a 20. század elejére már néhány száz darabosra bővült, ami az említett építkezéseken túl a budapesti polgárok ajándékozásainak volt köszönhető, akik felismerve házaikban vagy azok bontásakor a középkori faragványokat, azokat a múzeumnak adományozták.
Az 1930-as évektől kezdődő tudományos igényű régészeti kutatások, mint Garády Sándor budai ásatásai, vagy Lux Kálmánnak a belvárosi plébániatemplomban folytatott kutatása újabb emlékekkel gazdagították a gyűjteményt. Ekkor alakította ki Horváth Henrik a Halászbástya Kőtárat, ahol egyesítette az addig a városban rendszertelenül tárolt vagy bemutatott kőfaragványokat. Ez tekinthető a Vármúzeum elődjének is. Ekkor a mintegy 400 darabot bemutató kiállítás már Óbudáról és Pestről származó szobrokat és építészeti töredékeket is tartalmazott, vagyis átfogóbb képet adott a mai Budapest középkori történetéről.
A gyűjtemény robbanásszerű növekedését a második világháború utáni romeltakarítási és helyreállítási munkákhoz kapcsolódó régészeti kutatások eredményezték. Ekkor a palotaásatások során előkerült, nagyságrendileg 7000 darab faragott kő, valamint a budavári polgári házak romjai közül szórványosan előkerült darabok Magyarország legnagyobb középkori kőgyűjteményévé tették a múzeum kőtárát. Az 1960-as évektől újjáéledő régészeti kutatások, mindenekelőtt a Budapest területén található egykori kolostorok és királyi épületek kutatásának köszönhetően ez a szám mára megduplázódott, és mintegy 15000 faragványtöredék található ma a múzeumban, amelynek legjelentősebb darabjait a kiállításokon, nagyobb részét pedig raktárakban őrzik.