Territorially, the quaestura exercitus contained the Roman provinces of Moesia Inferior and Scythia Minor within the Diocese of Thrace, located in the lower Danube region, as well as the provinces of Cyprus, Caria, and the Aegean Islands within the Diocese of Asia. All of these provinces were detached from the Praetorian prefecture of the East and placed under the authority of a new army official known as the quaestor exercitus ("Quaestor of the army"). The authority of the quaestor was the equivalent to that of a magister militum. Since the strategically vital Danubian provinces were economically impoverished, the purpose of the quaestura exercitus was to help support the troops that were stationed there. By connecting the exposed provinces of the Lower Danube with wealthier provinces in the interior of the empire, Justinian was able to transport supplies via the Black Sea. This territorial restructuring relieved both the destitute populations and devastated countryside of the Danubian provinces from sustaining any stationed troops. There is a lack of subsequent evidence on the history of the quaestura exercitus. However, since the position of quaestor was still extant during the mid-570s, this indicates that the overall territorial unit achieved a modicum of success.
Ultimately, the Danubian provinces associated with the quaestura exercitus did not survive the Slav and Avar invasions of the Balkans in the 7th century. However, isolated fortresses on the Danube delta and along the coast of the Black Sea were maintained via supplies by sea. Charles Diehl first raised the suggestion that the great naval corps of the Karabisianoi, which appears in the 680s, was first formed by the remainders of the quaestura. This argument has been adopted by some scholars since but challenged by others, notably Helene Ahrweiler in her study of the Byzantine navy. This question is bound up with the discussion on the respective formations' nature as military-naval or civil-administrative entities.
Lead seals from Moesia Inferior and Scythia Minor provide evidence supporting the existence of the quaestura exercitus. Specifically, thirteen imperial seals (nine of which are from Justinian) demonstrate that communications between officials from Scythia Minor and Constantinople occurred on a somewhat regular basis.