Экспозиция музея в Костенках размещается в здании, специально построенном для этих целей в 70-гг XX века. До строительства стационарного каменного здания нужно было, каким-то образом, защитить сохраняемую стоянку от воздействия внешних факторов. Для этих целей силами археологической экспедиции и на средства Воронежского краеведческого музея стал сооружаться деревянный сарай, перекрывающий площадь раскапываемой стоянки.
Он представлял собой дощатое перекрытие, опирающееся на столбы-опоры, вкопанные в грунт. Поскольку с каждым новым квадратным метром раскопок автоматически увеличивалась охраняемая площадь, вкапывались новые столбы в заранее исследованные археологами ямки-зонды и продлевалось перекрытие.
В 1965 году по всему периметру раскопа стены были вымощены кирпичом, что предотвратило их от осыпания.
В целом эта конструкция была очень несовершенна: сквозь щели крыши постоянно затекал дождь и засыпался снег, что было особенно губительно в весенний период. Но, тем не менее, именно такое примитивное сооружение сохранило памятник в 60-е годы XX века. В 1967 году было принято решение о строительстве стационарного здания над раскопанной стоянкой. Проект этого сооружения был выполнен воронежским институтом «Воронежгражданпроект». Это было первое здание в области, построено специально для музея, причем такого необычного.
Перед его создателями стояла довольно сложная задача: нужно было построить помещение без внутренних опор, где не только был бы сохранен уже открытый культурный слой, но где в дальнейшем можно было бы проводить раскопки как внутри здания, так и снаружи вблизи его стен.
Одновременно нужно было грамотно привязать здание к местности: выделить из общей сельской застройки, но органично вписать его в уже сложившуюся пространственную планировку.
Проект музея, позже воплощенный в реальности, представлял собой простое сооружение, прямоугольные очертания объема которого подчеркивались простотой отделки стен с помощью штукатурки с каменной крошкой, бетонной скульптурой пасущихся мамонтов над входом и прямоугольными стеклянными окнами, идущими по периметру двух стен здания.
Главный объект музея – раскоп с остатками древнего жилища из костей мамонта – при такой планировке размещался свободно внутри здания, хорошо освещенный естественным светом, благодаря идущим
по фасаду окнам.
Но, самое главное, здание было построено свайным способом, без фундамента: кирпичные стены музея держались на восемнадцати железобетонных столбах-опорах, которые нижней своей частью уходили в грунт и держались на монолитных фудаментных «башмаках».
Для этих целей археологами в течение всего сезона производились исследования 18-ти шурфов, которые стали основанием для этих опор. С высоты нашего дня можно говорить о недостатках здания, о его слишком большой и плоской крыше, непригодной для климата наших широт.
Но в шестидесятые годы, когда музейно-архитектурное проектирование в нашей стране делало только первые шаги, это здание стало первым такого рода проектом в Воронежской области.
Построенное в 70-е годы здание служит музею до сих пор. Очень долго на протяжении двадцати лет его внутреннее наполнение представляло собой временную выставку, созданную в начале 80-х годов. Однако это не значит, что до этого не было попыток создания полноценной экспозиции. В середине 80-х годов в ленинградском институте «Росмонументискусство» под руководством О.А. Харченко был разработан очень интересный проект экспозиции. К сожалению, ей не суждено было воплотиться в жизнь.
В 2005 году экспозиция музея стала постепенно пополняться живописными реконструкциями. В 2009 году в музее открылся выставочный зал, где в том же году разместилась выставка, посвященная 130-летию исследования памятников Костенок. В 2010 году в музее появилась таксидермическая скульптура мамонта, выполненная в натуральную величину в мастерской московского музея «Ледниковый период». Весной 2011 года создан архитектурно-художественный фриз, на котором изображена реконструкция животного мира ледниковой эпохи и жизни людей палеолита, а также создана диорама «Поселение каменного века». Но самым главным и значительным экспонатом музея продолжает оставаться жилище из костей мамонта возрастом в 20 000 лет, законсервированное под его сводами.