Такое вольнодумство не очень пугало его. Участник Отечественной войны 1812 года и заграничных походов, Киселев жил теми же интересами, дышал той же атмосферой, что и его сверстники — будущие декабристы. На Киселева, вернувшегося на родину, Россия произвела такое же гнетущее впечатление, как и на них. В 1816 году он подал царю записку «О постепенном уничтожении рабства в России», в которой доказывал, что освобождение крестьян безусловно в интересах «коренного русского дворянства».
Александр I похоронил записку Киселева, как и многие подобные записки, а Киселев, который, по его собственным словам, свято исповедовал религию монархизма, не пытался найти другого пути для воплощения своих идей.
Либеральные настроения не мешали Киселеву очень заботливо относиться к своей карьере. В одном частном письме, давая характеристики всем генералам 2-й армии, Киселев и себе дал очень выразительную и меткую характеристику: «Умен, но еще более самонадеян, поэтому может принести пользу. Честен и готов жертвовать собой ради службы. При малейшем (вызванном им) недовольстве пожертвует всем, чтобы удовлетворить свое самолюбие». К этому можно было бы прибавить: «Старается сочетать либеральные идеи с интересами царской службы, но отнюдь не в ущерб службе и своей карьере».
Пестель тоже был обеспокоен назначением Киселева; при Рудзевиче положение как будто установилось, а что принесет с собой Киселев, неизвестно. У него возник план перейти на службу к командующему Бугскими военными поселениями генералу графу Витту, который предлагал ему у себя место начальника штаба.
В письме к отцу Пестель мимоходом упоминает об этом плане.
Иван Борисович был очень встревожен письмом сына. В ответном письме он доказывал, что не следует бросать службу у Витгенштейна и переходить к Витту. «Как менять верное на неверное? и если это неверное основывается на обещании — и кого? Графа Витта, который сам еще не оперился».
Взвесив все обстоятельства, Пестель ответил отцу, что мысль об уходе от Витгенштейна им пока оставлена.
Решив остаться во 2-й армии, Пестель попросил Рудзевича, ехавшего встречать своего преемника, отрекомендовать его Киселеву.
В письме из Херсона, где произошла встреча с Киселевым, Рудзевич сообщил: «Я все сделал, любезный Павел Иванович, что только чувство искреннего и дружеского моего к вам расположения указывает мне, отдав полную справедливость достоинствам вашим. Павел Дмитриевич Киселев сказывал мне, что он вас знает по репутации и много добра об вас говорил. Любя же вас много, вы можете представить себе, что я сим случаем умел воспользоваться».
Тульчин, небольшой городок в Подолии, населенный мелкой шляхтой, украинской и еврейской беднотой, принадлежал графу Мечиславу Потоцкому.
Въезд в город проходил по плотине обширного пруда. На берегу его в обрамлении стройных тополей высился костел, а за ним в густой зелени садов тонули стены старинного доминиканского монастыря и многоколонный дворец Потоцких с белыми флигелями и службами. За городом, то поднимаясь в гору, то опускаясь в долину, вился широкий, обсаженный четырьмя рядами деревьев Екатерининский шлях.
Пестель жил в особняке недалеко от дворца Потоцких. Внушительная внешность дома мало гармонировала со скромной обстановкой квартиры адъютанта главнокомандующего. Единственным ее украшением были полки с книгами. В кабинете хозяина стоял большой письменный стол, фортепьяно и кушетка. Пестель любил вечерами, не зажигая свечей, лежа на кушетке, курить трубку и размышлять или садился за фортепьяно и наигрывал что-нибудь из Глюка или Моцарта, незаметно начиная импровизировать. Он мог играть часами, за фортепьяно он забывал время.
Если заходили знакомые, они нередко все вместе отправлялись к Киселеву. Пестель был желанным гостем в доме начальника штаба. Здесь вечерами в гостиной киселевского дома вокруг Пестеля собирался кружок офицеров. Часто к ним присоединялся хозяин. Разговоры велись очень свободные. Не стеснялись высказывать свои мнения и о петербургском начальстве и об Аракчееве, а иногда касались и царской фамилии. Киселев слушал, улыбался, изредка вставлял свои замечания. Ему не боялись возражать, если находили, что он не прав, а он не обижался, выслушивая порой резкие возражения.
Свободное время Киселев нередко проводил в обществе Пестеля. Он охотно пользовался его богатыми знаниями, прекрасными способностями администратора. Их знакомство началось в день прибытия Киселева в Тульчин, 16 мая 1819 года, когда Витгенштейн представлял новому начальнику штаба своих сотрудников. Как адъютант главнокомандующего Пестель сопровождал потом Витгенштейна и Киселева в поездке по местам расположения 2-й армии, и эти поездки очень сблизили Пестеля и Киселева.