Шталь получил неплохое военно-морское образование. В 1885 г. он окончил штурманский отдел Технического училища Морского ведомства в Кронштадте (вскоре преобразованного в Морское инженерное училище императора Николая I), в 1890 г. — гидрографическое отделение Николаевской Морской академии, в 1896 г. — временный Штурманский офицерский класс, а в 1904 г. — курс военно-морских наук, созданный при Академии в 1896 г.
В 1885–1903 гг. он находился в заграничных плаваниях в Тихом океане и в Средиземном море. В должности штурмана крейсера «Забияка» занимался съемками побережья, получив навыки в самостоятельном проведении сложных гидрографических работ. Впервые же он участвовал в промерах на Онежском озере в период обучения в Техническом училище. В 1898–1903 гг. был старшим штурманским офицером на эскадренном броненосце «Полтава», а затем старшим офицером на эскадренном броненосце «Севастополь». В 1900 г. принимал участие в снятии с камней броненосца береговой обороны «Адмирал Апраксин», наскочившего на риф у южной оконечности острова Гогланд в Финском заливе. А.В. Шталь успел получить и боевой опыт, участвуя в подавлении боксерского восстания в Китае в 1898–1901 гг.
После окончания курса военно-морских наук в 1904 г. служил в стратегической части военно-морского учебного отдела Главного Морского штаба, а 1906 г., с образованием Морского Генерального штаба, занимал должность помощника начальника этого штаба. Служба в Главном Морском, а затем в Морском Генеральном штабе оставила заметный след в жизни Шталя. Здесь он проявил себя талантливым штабистом, разбиравшимся в формах и способах применения сил флота, в методах управления силами, и в совершенстве овладел методикой разработки планов операций и боевых действий. Ему приходилось исполнять множество боевых документов, контролировать их прохождение и обучать вновь прибывавших офицеров искусству штабной службы. При этом проявилась его склонность к научно-педагогической деятельности.
В соответствии с Наказом Морскому Генеральному штабу (основной документ, регламентировавший структуру и организацию деятельности Морского Генерального штаба) он включал в себя оперативную часть, отделения русской и иностранной статистики, военно-историческое отделение, а также делопроизводство по мобилизации флота. А.В. Шталю приходилось больше заниматься оперативной частью, в которых разрабатывали оперативные планы для Балтийского и Черноморского флотов и Сибирской флотилии. Однако ему приходилось много работать и в области военно-морской истории и истории военно-морского искусства. В эти годы специально созданной комиссией при Морском Генеральном штабе разрабатывался многотомный труд по описанию действий флота в русско-японскую войну 1904–1905 гг. и составлялись сборники документов по истории этой войны. Общее руководство авторскими коллективами осуществлял помощник начальника Морского Генерального штаба, то есть А.В. Шталь.