С началом войны 1914 года юноша поступает в школу прапорщиков в Кишиневе. Ситуация на фронте складывалась поначалу не в пользу стран Антанты, и, не дожидаясь окончания курса, командование отправило Лещенко в числе других учеников в действующую армию. По данным некоторых биографов, революция застала новоиспеченного офицера в госпитале, где он оправлялся после ранения. Период 1918–1919 годов в его жизни покрыт мраком. Есть основания предполагать, что он вступил в ряды Добровольческой армии и принимал участие в Гражданской войне на стороне белых. Сколь продолжительное время продолжалась «военная карьера» и каким образом завершилась, неизвестно. Так или иначе, но с весны 1920 года Лещенко зарабатывает на жизнь исключительно танцами и пением в составе различных трупп, разъезжая по Бессарабии (которая уже вошла к тому моменту в состав Румынии, сделав тысячи людей невольными эмигрантами). На афишах и открытках тех лет артист (почему-то) выведен под фамилией Мартынович. «Петрушка и Розика Мартыновичи — дуэт», — гласит подпись под рекламной фотокарточкой. Откуда взялась эта фамилия? Нет ответа. Хорошо знавшая Петра Константиновича певица Алла Николаевна Баянова вообще заявляет в своих воспоминаниях:
В 1925 году на гастролях в Париже Петр Лещенко познакомился с обворожительной танцовщицей из Риги Зинаидой Закис, дочерью богатого латышского коммерсанта.
Летом 1926 года они сыграли свадьбу и вскоре отправились в длительный гастрольный тур по Европе и странам Ближнего Востока. Семейный дуэт стал выступать вместе: оба танцевали, а Петр иногда пел, заполняя паузы между номерами.
Яркую пару ждал бешеный успех: внушительные гонорары и восторженные отзывы прессы. В Ливане состоялось их знакомство с Николаем Левицким и его юной дочерью. Впоследствии Алла Баянова так вспоминала тот вечер: