Во второй половине 1957 года двадцать семь МиГ-19П в разобранном виде были доставлены на чешскую авиабазу Кбелы. После сборки и облета эти самолёты передали чешским ВВС. Эти машины передали в те полки, где уже эксплуатировались МиГ-19С - 1-й Истребительный полк в Чешских Будейовицах и 11-й Истребительный полк в Затеке.
В середине 1958 года первые МиГ-19П поступили в одну из эскадрилий 28-го Истребительного полка ВВС Польши, базировавшегося в Слунс-Редзиково. Освоению самолёта мешало то, что поставленные Польше техническая документация и руководства по эксплуатации относились к модификации МиГ-19С... Польские МиГ-19П были впервые публично продемонстрированы во время авиационного парада 22 июля 1959 года. Когда в 1966 году поляки перевооружались на МиГ-21ПФМ, большая часть их МиГ-19П была передана Болгарии. Все польские МиГ-19П несли трехзначные бортовые номера красного цвета и знаки национальной принадлежности на задней части фюзеляжа, киле и нижней поверхности крыла. На верхнюю поверхность "шаховицы" не наносились.
В 1959 году десять МиГ-19П было поставлено в Румынию, которая годом позже получила ещё пять машин. На румынских пилотов самолёт впечатления не произвел, впрочем, как и на поляков. Только 66-я Истребительная авиадивизия в Деве-селуле была вооружена МиГ-19П и МиГ- 19ПМ. Позже это подразделение перебросили на авиабазу Борека. Сначала румынские МиГ-19П получили бортовые номера красного цвета с 001 по 015, но в 1965 году первую цифру в них поменяли с "0" на "7". Незадолго до снятия самолёта с вооружения первую цифру поменяли с "7" на "8". Знаки национальной принадлежности наносились на хвостовой части фюзеляжа, киле и нижней поверхности крыла. На румынских МиГ-19П, а позднее МиГ-19ПМ, верхняя поверхность корневой части крыла красилась в черный цвет. Основной задачей этих самолётов была противовоздушная оборона столицы Румынии Бухареста. Некоторые румынские МиГ-19П имели антенну ответчика ОРО-2 в носовой части по левому борту. Самолёты могли нести блоки ОРО-57К с неуправляемыми ракетами. Болгарские ВВС имели одну эскадрилью МиГ-19ПМ в составе полка ПВО, базировавшегося в Доброславицах. Первые самолёты этого типа поступили в 1966 году - это были бывшие польские истребители из 28-го и 39-го Истребительных полков. Болгарские МиГ-19П несли трехзначные бортовые номера без черной окантовки. Последние МиГ-19П были сняты с вооружения болгарских ВВС в 1975 году.
МиГ-19ПГ отличался от стандартного МиГ-19П наличием на борту аппаратуры "Горизонт-1", которая позволяла осуществлять наведение самолета на цель по командам с земли. Внешне самолет отличался наличием антенны системы "Горизонт-1" на левом борту. Кроме того, удлинили конический обтекатель антенны радара в воздухозаборнике и демонтировали антенну ответчика СРО-2 в носовой части.
В середине 50-х годов на вооружение советских ВВС была принята ракета воздух-воздух с радиолокационным наведением РС-2У (АА-1 Alkali). Сначала она использовалась на МиГ-17ПМ, ставшим первым в советских ВВС всепогодным истребителем с ракетным вооружением.