1872 году он получил чин поручика, а два года спустя – штабс-ротмистра и назначение на должность личным адъютантом командующего войсками Харьковского военного округа с зачислением по армейской кавалерии майором.
С началом Русско-турецкой войны 1877–1878 годов А. В. Квитка отправился в действующую армию и был прикомандирован вначале к 29-му Донскому казачьему полку, а затем к штабу 9-го армейского корпуса. Он особо отличился 30 августа 1877 года при взятии Гривицкого редута румынскими и русскими войсками в ходе третьего штурма Плевны: «Во время блистательной атаки Гривицкого редута, в самый критический момент, когда перед наступавшими выросла стена его, Квитка пошел так беззаветно и энергично, что всех увлек за собою, – иначе пункт этот обошелся бы нам гораздо дороже. Он в числе первых вскочил на бруствер редута вместе с флигель-адъютантом Шлиттером». В этой атаке Квитка получил ранение: «Майор Квитка, как говорят, вскочил верхом на неприятельскую пушку, но отделался лишь легкою огнестрельною раною в подмышку, без повреждения сочленений» (Старчевский А. А. Памятник Восточной войны 1877–1878 гг., заключающий в себе в алфавитном порядке биографические очерки всех отличившихся, убитых, раненых и контуженных: генералов, штаб- и обер-офицеров, докторов, санитаров, сестер милосердия и отличившихся рядовых. СПб., 1878.)
Заслуги А. В. Квитки в турецкую кампанию были отмечены производством в чин подполковника, награждением орденами Владимира 4-й степени с мечами, Анны 2-й степени с мечами и золотым Георгиевским оружием (за мужество при взятии Гривицкого редута). Впоследствии он опубликовал свои воспоминания о Русско-турецкой войне («Записки казачьего офицера»), вышедшие отдельной книгой в 1903 году. В дальнейшем подполковник А. В. Квитка принимал участие в Ахалтекинской экспедиции в Туркмению под началом генерала М. Д. Скобелева (в 1880–1881), проходил службу в Башкирском конном полку и Хоперском конном полку Кубанского казачьего войска и вышел в отставку в 1884 году.
Примерно в конце 1880-х годов Андрей Валерьянович женился на Вере Дмитриевне Мартыновой, родной племяннице Н. С. Мартынова, участника трагической дуэли с М. Ю. Лермонтовым 15 июля 1841 года. Брак оказался бездетным.
Находясь в отставке, значительную часть времени А. В. Квитка проводил в Италии и Южной Франции (из-за «непереносимости российских зим»), охотился на лис в окрестностях Рима, путешествовал, катался на яхтах. В Париже Андрей Валерьянович работал в художественной академии Жюлиана, а в 1897 году по представлению князей Трубецкого и де Маврокордато стал постоянным членом Клуба артистического Союза. Это был элитный клуб, членами которого являлись неравнодушные к искусству представители мировой аристократии. С этого времени подполковник принимал активное участие во всех мероприятиях, устраиваемых клубом в Париже: выставках, концертах, вечерах и т. и.
Помимо собственности за границей, А. В. Квитка приобрел имения на Черноморском побережье Кавказа, теплый климат которого как нельзя лучше подходил для него. Одно из них находилось в районе Туапсе, другое – между Сочи и Хостой. В своих новоприобретенных имениях супруги Квитки активно занимались виноделием, участвовали в выставках, а сам Андрей Валерьянович стал членом наблюдательного совета Варваринского училища плодоводства, виноградарства и виноделия.
В 1904 году, с началом Русско-японской войны, уже немолодой подполковник запаса подал прошение о направлении в действующую армию. Прошение было удовлетворено, и Андрей Валерьянович получил назначение во 2-й Нерчинский полк Забайкальского казачьего войска в чине войскового старшины на должность помощника командира полка по строевой части. Его супруга, Вера Дмитриевна, также отправилась на театр военных действий в качестве сестры милосердия в санитарном поезде императрицы Александры Федоровны.
С мая по ноябрь 1904 года А. В. Квитка участвовал в боевых действиях в составе отряда генерал-майора П. К. Ренненкампфа, действовавшего на левом (восточном) фланге русской Маньчжурской армии, а затем, в ноябре-декабре того же года находился в 1-м Верхнеудинском полку Забайкальского войска в отряде генерала П. И. Мищенко, который обеспечивал прикрытие русского правого (западного) фланга. В январе 1905 года, находясь на лечении в госпитале, он получил известие о присвоении ему чина полковника. Но участвовать в боях с японцами Андрею Валерьяновичу более не довелось. Из-за развившегося плеврита в марте того же года он был эвакуирован из Харбина в Россию, получил разрешение выехать для лечения за границу, а в августе, по заключении мира с Японией, второй раз вышел в отставку.
В биографической справке в альбоме «Белая Армия. Фотопортреты русских офицеров 1917–1922» (YMCA-PRESS, 2007) говорится об участии А. В. Квитки в Первой мировой войне в рядах лейб-гвардии Конного полка и в Гражданской войне в составе Добровольческой армии, однако, принимая во внимание уже преклонный к тому времени возраст и состояние здоровья Андрея Валерьяновича, в эти утверждения трудно поверить. Опубликованный в том же альбоме фотопортрет А. В. Квитки, где бравый полковник с повязкой на левом глазу запечатлен в защитной фуражке и френче со стояче-отложным воротником, при погонах и орденах, можно датировать периодом 1916–1920 годах и позднее, однако поскольку офицеры выходили в отставку с правом ношения формы, эта фотография