Эрнест Соколкин, павлодарский краевед, вспоминает, что это не первая и даже не вторая попытка присвоить городу новое имя. Сначала «Павлу в дар» не давал покоя властям страны Советов. Первые попытки были в 20-х годах, тогда выбирали между Ленинском и Ленинском на Иртыше, затем избавиться от упоминания в названии города имени князя Павла (сына императора Александра II) попытались в следующем десятилетии.  
– Вторая волна настигла город в 30-х годах, тогда хотели переименовать Павлодар в Ворошиловск, – рассказывает Эрнест Соколкин. – Но все попытки как-то сошли на нет. Казахстан же многоязычная страна. Многонациональная. Здесь должны быть названия трех-четырех этносов, а не одного!
Однако у павлодарских чиновников иное мнение. Они упорно вот уже на протяжении нескольких лет пытаются доказать обратное: переименование – дело государственной необходимости. Чиновники полагают: региональный центр должен носить сугубо историческое название. Только вот с историей они еще не определились.  
– Конкретных вариантов сегодня нет, но предложений к нам поступает очень много, – говорит начальник управления развития языков Павлодарской области Талгат Абылкасымов. – Я думаю, что нужно переименовать, потому что этого требует наша сегодняшняя история. Казахстан – независимое государство, и название должно быть близко связано с историей Павлодарской области.
Но чиновники лукавят, утверждая, что конкретных вариантов нет. Буквально год назад вариант был. Город хотели переименовать в Кереку. Тогда павлодарских историков захватил сумасшедший ажиотаж: одни взахлеб доказывали историческую правомерность нового названия, другие утверждали, что созвучное с петушиным криком слово – полная нелепица.
Сотни трудов и диссертаций было написано в защиту Кереку, ученые доказывали, что это слово образовалось от названия племени, когда-то проживавшего на территории Казахстана. От подобной псевдонауки учителя старой закалки пришли в шоковое состояние. Не мог и до сих пор не может понять учитель-историк, отличник образования Казахской ССР, ныне пенсионер из села Пресное Павлодарской области Марат Кожимов, кому и зачем понадобилось переписывание учебников по истории Казахстана. Бывший учитель очень удивился, когда обнаружил, что в новой книге для пятиклассников «Города Казахстана» среди всех названий отсутствует родной Павлодар. Такой обиды пенсионер не мог стерпеть и даже написал письмо в местную газету:
«Я изложу свою позицию как сторонний наблюдатель, прочитавший ряд публикаций в казахскоязычной и русскоязычной прессе. Самый верный, объективный подход к разрешению таких спорных вопросов должен заключаться в наличие достоверных источников, исторических фактов. Все остальное – гипотезы, догадки, мифы и легенды, передающиеся из поколения в поколение, сказания и предания – просто сказочная фантазия и словесная «бутафория». К сожалению, подобная «мифология» частенько берется за основу современными доморощенными историками при написании ими псевдонаучных исторических «шедевров», где много лжи и фальсификации...»
На самом же деле Кереку – это переиначенное на казахский язык русское название «Коряковка», именно так когда-то назывался форпост на Иртыше, ставший  впоследствии Павлодаром.
– Русский купец Коряков приехал сюда из города Тары за солью, – рассказывает краевед Эрнест Соколкин. – Нашел озеро, его позже назвали Коряковским, и заложил здесь первую солесыпку. Обрыв на этом месте около озера назвали Коряков яр. А позже, когда строились форпосты, в 1720 году на месте Корякова яра решили заложить форпост, которому дали имя Коряковский.
Позже Коряковский форпост был преобразован в станицу. А в 1861 году Коряков получает статус «заштатного города с наименованием оного Павлодар, в честь новорожденного Великого князя Павла Александровича». Преподнести город в дар Павлу предложили местные предприниматели. В своем письме к императору купцы попросили назвать город «Павлу в дар»: они посчитали, что после такого названия станица обязательно получит статус города, и не ошиблись. Однако в Петербурге решили, что «Павлодар» звучит гораздо лучше, чем предложенный купцами вариант.
Доказывать очевидное, что Павлодар – единственное историческое название – приходится и сейчас. Об этом не понаслышке знает старейший журналист Павлодара Юрий Ковхаев – не один свой материал он посвятил борьбе за славное имя города. Журналист считает, что переименование носит сугубо националистический характер.
– О каких исторических корнях названия Павлодара можно говорить, если с самого начала существования города он был назван сразу же Павлодаром? – возмущается Юрий Ковхаев. – Название «Павлодар» и есть историческое. Совершенно ясно, что за этим стоят не поиски каких-то исторических корней, а иные мотивы. Я думаю, эта возня чисто националистического характера. Потому что иного объяснения этой кампании просто нет. Искать какое-то рациональное зерно бессмысленно.
Чиновники уверяют: от идеи присвоить городу имя «Кереку» уже отказались. Возможно, разум взял вверх в головах госслужащих, а может быть, это всего лишь временное затишье. Но несмотря на то, что город еще не переименовали, в новостях на государственном языке журналисты уже называют Павлодар – Кереку.
Другой немаловажный вопрос переименования – это экономическая составляющая. Все расходы по изменению имени родного города лягут прежде всего на рядовых павлодарцев. Депутат павлодарского городского маслихата Мирхат Серекбаев относительно переименования еще четко не определил свою позицию, но народный избранник считает, что сейчас говорить о переименовании пока не стоит.
– С экономической точки зрения считаю, что это нецелесообразно, – говорит депутат. – Получается, каждому жителю города придется менять множество документов, юридическим лицам менять реквизиты, на трассах – указатели. Это нам обойдется очень дорого, поэтому вопрос о переименовании пока поднимать не стоит.


С 1 июля прошлого года из-за кризиса правительство Казахстана ввело мораторий на переименования. Однако в Министерстве культуры и информации утверждают –  даже мораторий не помеха.  
– Да, у нас есть мораторий, но если доказана необходимость переименования, что это  государственная важность, то принимать решения можно, – говорит председатель комитета по языкам Министерства культуры и информации Казахстана Ербол Шаймерденов. – Но что касается переименования Павлодара, пока на официальном уровне такой вопрос не ставился.
Между тем в самом Павлодаре на повестках ономастических комиссий то и дело встает вопрос о переименовании города на Иртыше. Кстати, среди обсуждаемых названий есть и название протекающей здесь реки – только на казахский манер – Ертыс. Также поступали предложения назвать город Кимак, по названию проживавшего на территории Казахстана племени, или в честь президента республики Нурсултана Назарбаева – Нуркент.  Переименование подогреет эмиграционные настроения русскоязычной среды, считает Юрий Ковхаев. Солидарен с журналистом и историк Марат Кожимов.
– Для всех казахстанцев многонациональный Казахстан – наш большой общий дом. Но есть еще и малая родина, где мы живем, – это Павлодар. Как можно сохранить мир и спокойствие в нашем доме, если «патриоты» с узконациональной амбицией, своими антироссийскими измышлениями и попытками очернить весь советский период истории казахов, невольно сеют раздор и смуту в мыслях и душах людей, особенно молодежи? Чего хотят эти «ученые мужи»?»
Чиновники утверждают: к ним обращается множество павлодарцев с просьбой переименовать город. Только вот официальные данные о том, каков процент населения за избавление от «Павлова дара», почему-то нигде не афишируется. Павлодарский Славянский центр решил сам провести анкетирование и узнать, действительно ли народ за переименование? Из  пяти тысяч опрошенных респондентов только 16 человек одобрили идею переименования, количество сторонников не превышает и одного процента!
– Мы раздали эту анкету по городу. Ее заполняли казахи, татары, немцы. Однако чиновники нам сказали: ваши данные неофициальные и нечего ими манипулировать, – говорит председатель Славянского центра Татьяна Кузина. – Конечно, они неофициальные – это же общественное мнение, мы спрашивали его у народа. Я категорически против переименования. Очень грустно от того, что муссируют этот вопрос. Чем им Павлодар не угодил?  
Волна переименований охватила Казахстан сразу после приобретения независимости. Переименовывались области, города, улицы. Последнее крупное переименование состоялось в 2007 году. Семипалатинску, основанному в 1718 году, дали новое имя – Семей. Этот шаг президент Казахстана Нурсултан Назарбаев мотивировал тем, что ассоциации с Семипалатинском возникают не самые радужные – Семипалатинский ядерный полигон, и это отпугивает потенциальных туристов.