Armistead Rust nació en el condado de Campbell , Virginia , el 12 de julio de 1862. Fue nombrado ingeniero cadete en la Academia Naval de los Estados Unidos el 1 de octubre de 1881. Después de completar el curso de instrucción, fue separado de la Academia Naval el 1 de junio de 1885. esperar órdenes para los dos años de servicio marítimo que precedieron a la graduación en ese momento. Después del servicio en Tennessee y Richmond , regresó a Annapolis en la primavera de 1887 para graduarse, recibió su diploma el 15 de junio de 1887 y fue comisionado como alférez el 1 de julio de 1887.
Durante los siguientes tres años, Rust sirvió sucesivamente en la Oficina de Navegación y en las balandras de guerra Saratoga , Constellation y Jamestown . En diciembre de 1890, comenzó una misión en tierra. Después de cuatro meses de servicio de artillería en el Washington Navy Yard , se presentó en el campo de pruebas navales en Indian Head, Maryland , el 7 de abril de 1892 para un servicio similar. En septiembre de 1892, Rust se fue a casa con una licencia de un año. A su regreso al servicio activo a fines de agosto de 1893, Ens. Rust se hizo a la mar en Pinta . siguiente deber en relación con la nueva puesta en servicio de lacrucero blindado Boston en septiembre y octubre de 1895 y una breve asignación a Ranger desde finales de octubre hasta principios de diciembre, fue trasladado a Monterey y sirvió en ella hasta septiembre de 1896 cuando se fue a casa con tres meses de licencia. A fines de noviembre de 1896, la Ens. Rust comenzó otra asignación de artillería en Indian Head.
El recién ascendido teniente (jg.) Rust fue separado del campo de pruebas el 11 de noviembre de 1897 y se presentó a bordo de la cañonera Newport una semana después. Durante la Guerra Hispanoamericana , sirvió sucesivamente en Newport , Hist y Princeton . El 10 de junio de 1899, Rust fue ascendido a teniente mientras aún servía en Princeton . Entre enero de 1900 y marzo de 1901, el teniente Rust sirvió en Don Juan de Austria y Scindia . Después de un período de servicio en tierra en Bath, Maine , como inspector de equipos y artillería, regresó al mar en Montgomery .en julio de 1902 y sirvió en ella hasta septiembre de 1904. Luego de una asignación a Minneapolis entre noviembre de 1904 y enero de 1906, el teniente comandante. Rust se mudó a tierra una vez más como instructor de artillería en Washington Navy Yard.
En noviembre de 1907, informó a la Oficina de Equipos en Washington junto con los preparativos para un levantamiento hidrográfico de la costa sur de Cuba entre Cabo Cruz y Casilda . teniente comandante Rust dirigió esa misión durante los primeros cinco meses de 1908 e informó a Washington en junio. A fines de octubre, regresó a Cuba para retomar la dirección del levantamiento hidrográfico y asumir el mando de Hist . Fue ascendido a comandante el 4 de noviembre de 1908. Comdr. Rust completó su gira de servicio hidrográfico en octubre de 1910 y fue a Louisiana ( Battleshipnº 19). Fue separado de ese buque de guerra en agosto de 1911 y pronto comenzó dos meses de servicio temporal en la Oficina de Artillería . El 26 de octubre de 1911, Comdr. Rust asumió el mando del USS Baltimore ( Crucero No. 3) con funciones adicionales como capitán del astillero en el Charleston Navy Yard .