Главной темой творчества А. Клименко стала история Древней Руси. «Во многом мною движут протест, возмущение против нынешнего национального унижения России и русских. Немного найдётся народов, ныне живущих на земле, кто имел бы многотысячелетнюю историю, подобную нашей, и сделал бы такой вклад в мировую культуру. Нельзя же быть иванами не помнящими родства и поддакивать рассказам о дикости наших предков, будто бы лазавших ещё по деревьям, когда в Европе уже расцветала цивилизация», – считает художник.

Сюжеты для своих картин он черпает в произведениях историков XIX века, таких как А. Нечволодов, Е. Классен, И. Забелин, а также в русских народных сказках. «Именно в мифы и сказки любой народ всегда вкладывал своё понимание добра, красоты, мужества, мужской и женской чести, – говорит художник. – Для детей здесь открывается целый волшебный мир, в котором они учатся постигать красоту и смысл искусства».

Андрей Леонидович думает, что сегодняшнему обществу не хватает героев – тех, что своими подвигами могли бы пробудить человечество. Один из любимых героев живописца – Иван-дурак. Почему? «Его "величают" так все те, кто себя считает умным. Потому что он не такой, как все, то есть ненормальный, ибо способен на риск в отличие от безнадёжно нормальных, способен на благородный поступок», – уверен художник. Он изображает битвы, героев истории и сказок, полководцев античности и Средних веков. «Конечно, изображение отрубленных голов и живописное воспевание поля после битвы, усеянное погибшими воинами, не совсем этично, – соглашается Клименко. – Но в гуманистическом искусстве именно такое изображение способно вызвать в человеке положительную эстетическую реакцию, утверждая величие жизни».