Палеонтологическая коллекция формируется с основания музея и насчитывает свыше 300 экспонатов, найденных на территории Алтая.
В экспозиции представлена тазовая кость мамонта, найденная в 1908 году гражданином Саузовым. Среди экспонатов коллекции: черепа шерстистого носорога, ископаемого бизона, рога большерого оленя, нижние челюсти мамонта, фрагмент нижней челюсти мамонтёнка с видимой сменой зубов; из последних поступлений – полный скелет зубра. Есть в палеонтологической коллекции музея и уникальные древние окаменелости, отпечатки флоры и фауны, найденные на Алтае в районах рек Шинок, Коргон, на Кондратьевской сопке и др. Их возраст насчитывает более 300 миллионов лет.
На территории Алтая к началу палеозоя (около 570 млн.лет назад) был обширный морской бассейн с островными цепями вулканов. С конца кембрия (самого древнего периода палеозоя, продолжавшегося 65 млн.лет) начались сильные горообразовательные движения, связанные с вулканической деятельностью, что привело к значительному уменьшению площади водоемов, а в девоне (400 млн. лет назад) вулканическая деятельность стала еще более энергичной.
К концу девона происходит обмеление моря, возникает складчатая страна с многочисленными действующими вулканами. В связи с высыханием водоемов, их обитатели массово гибли, и морские осадки девона содержат многочисленные отпечатки и окаменелости ископаемой фауны того периода. Отложения с ископаемой фауной встречаются во многих местах Алтая, но особенно характерными являются глинистые, известково-глинистые сланцы Кондратьевской сопки около с.Куяган, где отмечены находки с обильными отпечатками кораллов, мшанок, трилобитов, морских лилий, окаменевшие раковины головоногих моллюсков и очень интересные образцы с отпечатками чешуи девонских рыб.
В палеонтологической коллекции отдела природы девонский комплекс ископаемой фауны представлен достаточно полно и дает зрительное представление о внешнем виде, строении и размерах древних морских обитателей.
К началу мезозоя (230 млн. лет назад) Алтай окончательно сформировался в горную страну. Море отступило и больше не возвращалось. Вулканическая деятельность прекратилась. В этот период покоя Алтай подвергся сильному разрушению и превратился в равнину-пенеплен, который был покрыт массой озер и отдельными возвышенностями, поэтому на Алтае нигде не найдены осадочные породы мезозоя, где могли бы сохраниться следы мезозойской фауны и флоры.
Кайнозойская эра Алтая (в палеонтологическом отношении) особенно интересна многочисленными костными останками крупных млекопитающих четвертичного периода (1,7 млн. лет назад). Начало его – плейстоцен – характеризовался резким снижением температуры, образованием ледников, которые то наступали, то отступали, и это происходило неоднократно. В холодных условиях явное преимущество получили крупные животные, которым было легче сохранить тепло. По названию самого крупного представителя млекопитающих плейстоцена - мамонта - и происходит название фауны того времени - “мамонтовая”.
В палеонтологической коллекции отдела природы мамонтовая фауна представлена наибольшим количеством экспонатов (около 70 экз. только основного фонда). Это, прежде всего, коллекция нижних челюстей мамонта, среди которых есть уникальный экземпляр – нижняя челюсть мамонтенка с видимой сменой зубов. Кроме того, большая коллекция зубов мамонта в разные периоды его жизни, бивни, позвонки, ребра, бедренные, плечевые, тазовая и лопаточная кости. Последним приобретением отдела является затылочная часть головы мамонта хорошей сохранности.
Останки шерстистого носорога представлены коллекцией верхних черепных крышек животного, позвонками, бедренной и лопаточной костями.
Самой многочисленной является коллекция верхних черепных крышек ископаемых бизонов, среди которых можно выделить две основные ветви – степную и лесную, которые внешне отличаются формой и размерами рогов.
Кроме того, в палеонтологическую коллекцию плейстоцена входят: фрагменты рогов исполинского оленя и очень редкая находка – верхняя черепная крышка первобытного тура.
Палеонтологическая коллекция отдела природы дает зрительную и обоснованную историю геологического прошлого Алтая. На основе этой коллекции в музее проводятся лекции по темам “Развитие жизни на Земле”: “Живое прошлое Земли” (о млекопитающих четвертичного периода), “Часы планеты” (о геологической истории Земли и Алтая в частности).