Будущий генерал-хорунжий УНР родился в 1878 году в Тифлисе в семье артиллерийского генерала Владимира Павленко и грузинской дворянки. Михаил, как и его младший брат Иван (также ставший заметной фигурой украинского движения), при рождении носил фамилию Павленко. Омельяновичем он стал, когда ему было уже за 30 лет, на волне увлечения историей казачества. В 1912 году братья взяли себе фамилию в честь деда Омельяна (Емельяна) Павленко — сотника из задунайских казаков.
После учебы в Омском кадетском корпусе Михаил Павленко поступил в Павловское военное училище — одно из самых престижных пехотных учебных заведений, которое он окончил в числе лучших (по 1-му разряду). Выпускавшиеся по первому разряду зачислялись в гвардейские полки.
Павленко в звании подпоручика попал в лейб-гвардии Волынский полк. С началом Русско-японской войны он перевелся из гвардии в обычную пехоту, чтобы принять участие в боевых действиях на Дальнем Востоке. Из командировки Павленко вернулся в гвардию с ранением и несколькими наградами.
Волынский полк он больше не покидал и встретил Первую мировую в звании гвардейского капитана и командира роты этого полка. В ноябре 1914 года после тяжелого ранения он по состоянию здоровья вынужден был покинуть свою часть и в дальнейшем служил в штабе гвардейского корпуса. Но и его он покинул в 1916 году после тяжелой болезни.
38-летний Павленко был признан негодным к дальнейшей строевой службе и отправлен в тыл. Как и большинство подобных офицеров, он был назначен начальником школы прапорщиков, которые ускоренным порядком готовили офицерские кадры для фронта. Полковник Павленко возглавил Одесскую школу прапорщиков, там и встретил Февральскую революцию.
До революции Павленко был на хорошем счету в императорской армии. Безупречная служба в гвардии, звание полковника в 38 лет, целая россыпь наград: от ордена Св. Владимира до Святого Георгия 4-й степени, несколько боевых ранений. Разве что увлечение историей казачества могло стать намеком на дальнейшую деятельность Павленко.
Сразу же после революции он оказался в числе первых сторонников украинизации армии и был едва ли не первым офицером в таком звании, который участвовал в политических митингах и манифестациях под желто-голубым флагом. «Одесский листок» писал: «Во время вчерашней манифестации Одесса была удивлена неожиданностью. Популярный начальник Второй одесской школы прапорщиков, полковник гвардии, георгиевский кавалер… вел свою школу под сепаратистским "украинским флагом"». Любопытно, что тогда же одним из офицеров этой школы был Михаил Муравьев, прославившийся позднее как первый красный завоеватель Киева.
Как и гетман Скоропадский, Павленко не столько был украинцем, сколько сознательно решил сделаться им (мовы он не знал, родился на Кавказе, всю жизнь служил в России и в Польше, с осени 1916 года служил в Одессе).
