День окончания школы совпал со страшным днем начала войны: 22 июня 1941 г. Павел Александрович поступает в школу летчиков  в Уфе, но затем его переводят в Златоустовскую школу инженеров-саперов. Получив звание лейтенанта и навыки в подрывном деле, его отправляют на фронт, в район Великих Лук. Сначала Гачегов был командиром взвода, потом роты 25-го гвардейского отдельного саперного батальона, с которой прошел нелегкий путь от Великих Лук до Кенигсберга.

За захват и разминирование мостов при освобождении Витебска получил орден Красного Знамени лично из рук командующего фронтом генерала армии И.Д. Черняховского.

Был трижды ранен, но все время возвращался в строй, на военную службу. После тяжелого ранения в 1945 г. был признан инвалидом, но в 1950 г. вернулся в строй. В госпитале г. Шарья Костромской обл., где проходил лечение, познакомился с будущей женой – Александрой Ивановной.