Начало военной карьеры
Али-Ага Шихлинский родился 23 апреля (3 марта) 1865 года в небольшом селении Казахлы Казахского уезда Елизаветпольской губернии (ныне село Ашагы Салахлы Казахского района Азербайджана) в семье помещика. Происходил из древнего дворянского рода, первое упоминание о котором относится к 1537 году. Мать Шах-Йемен ханум была внучкой известного поэта Молла Вели Видади.
В августе 1876 года поступил в военную гимназию в Тифлисе (ныне Тбилиси), впоследствии переименованную в Кадетский корпус, который окончил в 1883 году. Военную службу начал 1 сентября 1883 года юнкером Михайловского артиллерийского училища в Санкт-Петербурге. По окончании училища по первому разряду, 11 августа 1886 года высочайшим приказом Али Ага Шихлинский был произведен в подпоручики и получил назначение в 39-ю артиллерийскую бригаду, дислоцированную на Кавказе в городе Александрополе (ныне Гюмри). Службу начал в 5-й, затем во 2-й батарее, а в конце октября был назначен преподавателем бригадной учебной команды, готовившей фейерверкёров, то есть унтер-офицеров. 23 ноября 1887 года был произведен в поручики, а в апреле 1891 года получил свою первую награду — орден Св. Станислава 3-й степени.
15 июля 1894 года А. Шихлинский был произведен в штабс-капитаны и в сентябре был назначен заведующим бригадной учебной командой. С 1 февраля 1895 года старший офицер 1-й батареи. В феврале 1896 года награждён орденом Св. Анны 3-й степени. С 19 июля 1898 года А. Шихлинский капитан. С июня 1899 года по февраль 1900 года временно исполнял обязанности командира 1-й батареи.
В начале 1900 года Али Ага решает перевестись служить в Восточную Сибирь. 17 февраля последовал высочайший приказ о переводе капитана А. Шихлинского в Отдельный Забайкальский артиллерийский дивизион. Отправившись к новому месту службы 14 марта 1900 года, Шихлинский прибыл в дивизион 17 мая и был назначен старшим офицером 1-й батареи. Отдельный Забайкальский артиллерийский дивизион состоял из двух батарей: 1-й батареей командовал полковник В. И. Энгельман, 2-й — подполковник Самедбек Мехмандаров. В связи с нехваткой офицеров во 2-м Восточно-Сибирском летучем артиллерийском парке (тыловое подразделение, имевшее запасы боеприпасов) Шихлинский некоторое время исполнял обязанности командира парка. В составе Отдельного Забайкальского артиллерийского дивизиона принял участие в китайском походе. За отличие в делах против китайцев 1 мая 1901 года А. Шихлинский был награждён орденом Св. Станислава 2-й степени с мечами.
С мая 1901 года по март 1902 года А. Шихлинский исполнял обязанности командира 1-й батареи и командира дивизиона. В мае-июне 1902 года временно командует 2-й батареей, а в июле назначается старшим офицером этой батареи. С августа того же года по октябрь 1903 года командует 2-й батареей, заменяя убывшего в шестимесячный отпуск и на учёбу в Санкт-Петербург полковника С. Мехмандарова.
Русско-японская война
Русско-японскую войну А. Шихлинский встретил в должности старшего офицера батареи. После назначения в феврале 1904 года полковника С. Мехмандарова командиром 7-го Восточно-Сибирского стрелкового артиллерийского дивизиона капитан Шихлинский был временно назначен командиром батареи. Принимал участие в боях на Цзиньжоуском перешейке и Волчьих горах. Однако остановить японцев на этих рубежах не удалось, понеся значительные потери и не получив подкрепления части 4-й Восточно-Сибирской стрелковой дивизии и поддерживающей её 4-й Восточно-Сибирской стрелковой артиллерийской бригады, в состав которой к этому времени вошёл Отдельный Забайкальский артиллерийский дивизион, вынуждены были отойти к Порт-Артуру. 17 июля 1904 года все части дивизии отошли в район крепости Порт-Артур. Началась осада крепости японской армией.