Дороги войны приводят юного географа в Мурманское военное училище связи, где многие вопросы были для него знакомы по педагогическому вузу. После успешного окончания еще одного учебного заведения молодой лейтенант Будун в составе 78‑й Краснознаменной стрелковой дивизии прошел ратными военными дорогами России, Украины, Белоруссии, Венгрии, Чехословакии, Австрии.
Военная специальность связиста обязывала молодого офицера быть физически здоровым, выносливым, готовым в любую минуту по приказу командования прокладывать связь по самым сложным условиям рельефа и местности. На войне как на войне. Были будни, были успехи, поражения, неудачи, ранения, госпитали. Но молодой офицер-связист не унывал и всякий раз с оптимизмом принимал все невзгоды военной жизни. Характерно, что он в самых сложных ситуациях всегда находил выход из создавшегося положения, куда бы не забрасывала военная судьба.
Войну Анатолий Семенович заканчивает в звании подполковника. Его грудь украсили 5 орденов и около двух десятков медалей.