Воспитывался во 2-м Петербургском кадетском корпусе, директором которого был его отец А. А. Клейнмихель. Выдвинулся, главным образом, благодаря Аракчееву, при котором состоял адъютантом, а затем начальником штаба военных поселений. В 1826 году назначен генерал-адъютантом и членом комиссии по составлению Устава пехотной службы. Пользовался особым доверием и расположением императора Николая I. В 1838 году ему поручена была перестройка Зимнего дворца после пожара, что он и исполнил с замечательной быстротой. По этому случаю была выбита в честь Клейнмихеля золотая медаль с надписью: «Усердие все превозмогает».
В начале 1842 года Клейнмихель исполнял должность военного министра, а в конце того же года назначен главноуправляющим путями сообщений и публичными зданиями и оставался в этой должности до октября 1855 года. За время управления Клейнмихелем этим ведомством окончен постоянный мост через Неву (Николаевский), выстроено здание нового Эрмитажа, проведена Николаевская железная дорога и прочее. Казенные постройки во времена Клейнмихеля возводились быстро. По восшествии на престол Александра II, Клейнмихель был одним из первых деятелей предыдущего царствования, уволенным от должности; он был назначен членом государственного совета, в делах которого почти не принимал участия.
При строительстве одного из мостов через Неву в период царствования Николая I несколько тысяч человек были заняты забиванием свай. Не говоря уже о громадных расходах, это крайне замедляло ход работ. Искусный строитель генерал Станислав Валерианович Кербец пораскинул своей умной головой и выдумал машину, значительно облегчившую и ускорившую этот воистину египетский труд. Успешно проведя испытания, генерал представил описание машины главноуправляющему путей сообщения графу Петру Андреевичу Клейнмихелю и ждал по крайней мере благодарности. Граф не замедлил с ответом. Кербец получил официальный и строжайший выговор ретивого министра: почему, дескать, не изобрёл эту машину раньше и потому ввёл казну в огромные расходы.