1 декабря 1988 года произошёл очередной случай захвата заложников. Банда из четырёх человек во главе с рецидивистом П. Л. Якшиянцом (его подручные — Владимир Муравлёв, Герман Вишняков и Владимир Анастасов) захватили пассажирский автобус ЛАЗ-697, в котором находились ученики 4-го класса «Г» школы № 42 вместе с учительницей Н. В. Ефимовой — среди заложников были жена Якшиянца Т. М. Фотаки и его дочь. Террористы перегнали автобус из Орджоникидзе в аэропорт Минеральных Вод. 2 декабря в 0:10 командир прибывшей группы «Альфа» Г. Н. Зайцев по рации начал вести восьмичасовые переговоры с Якшиянцом, от которого услышал требования: предоставить ему самолёт для вылета в Пакистан, Израиль или ЮАР. Также Якшиянц требовал освободить своих осуждённых сообщников в Ташкенте, дав всего 40 минут на размышление и угрожая убивать по одному заложнику каждые полчаса. Павел предусмотрел возможность штурма автобуса, поэтому поставил трёхлитровые банки с бензином: при малейшей искре автобус взорвался бы, не оставляя шансов выжить никому из заложников. Изначально договорённость была достигнута о перелёте в Пакистан с промежуточной посадкой в Ташкенте — ради этого был выбран самолёт, который изначально должен был лететь в Дели. Однако позже Якшиянц наотрез отказался от Пакистана, объяснив это тем, что СССР фактически воюет против Пакистана (на территории страны располагались базы, где обучались афганские моджахеды), и заявил о необходимости лететь в Израиль, выдвинув ещё одно требование — миллион долларов США, миллион фунтов стерлингов и «миллион золотом». После переговоров Якшиянца уговорили принять 2 миллиона долларов в обмен на обещание отпустить заложников. Позже Якшиянц выдвинул очередное требование — предоставить ему семь заряженных боевыми патронами автоматов типа АКМ и восемь бронежилетов, несмотря на запрет на перевозку оружия за рубеж гражданскими рейсами, но предоставлять гарантии освобождения детей отказался. В связи с настаиванием Якшиянца на восьми бронежилетах группа «А» долгое время думала, что террористов всего восемь.
Переговоры заходили в тупик, так как Якшиянц настаивал на том, чтобы привести кого-то из членов Политбюро или лично Р. М. Горбачёву, обязательно требуя от М. С. Горбачёва подтверждения того, что всем четверым дозволено вылететь в Израиль[81]. По истечении 9-го часа переговоров на связь вышли сотрудник УГКБ по Ставропольскому краю Е. Г. Шереметьев и сотрудник группы «А» В. А. Бочков: к тому моменту Якшиянцу предоставили гарантии выдать четыре пистолета Макарова и один автомат Калашникова, а также подготовили экипаж Ил-76Т (RA-76519) во главе с Александром Божковым для вылета. После выдачи пистолетов, автомата и четырёх бронежилетов Якшиянц отпустил ряд заложников, оставив 10 мальчиков и учительницу. Затем к самолёту подвели жену Павла Тамару, которая убедила его отпустить остальных детей и учительницу, оставив на борту только экипаж и Шереметьева, но позже под давлением Якшиянц вынужден был отпустить и Шереметьва. Всего на освобождение заложников Шереметьев потратил шесть часов, а Ил-76 вылетел в Тель-Авив. По каналам МИД СССР Израиль, не имевший дипломатических отношений с СССР, дал «добро» на выдачу преступников, и после приземления самолёта в аэропорту «Бен-Гурион» всех бандитов задержала израильская полиция по обвинению в терроризме, а у Якшиянца конфисковали оружие и деньги, которыми он пытался откупиться. В операции по задержанию бандитов участвовали руководитель советской консульской группы Мартиросов и второй секретарь МИДа Израиля Я. Кедми. Всех четверых бросили в тюрьму Абу-Кебир. Изначально депутаты Кнессета выступали против депортации банды Якшиянца в СССР, настаивая на подробном выяснении всех обстоятельств задержания, но позже согласились выслать всех четверых в Москву в обмен на неприменение в их отношении высшей меры наказания. Якшиянц в итоге получил 15 лет лишения свободы. Начиная с этого момента в дни каждого национального праздника Израиля охрану его посольства обеспечивала «Альфа».