Presburger introduced his arithmetic in 1929 the paper was translated into English in 1991. Here is the citation to this paper:

* M. Presburger. _Ueber die Vollstaendigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt._ C.R. du I Congr. des Math. des pays Slaves, Warszawa, 1929, pp.92-101

Here is the English translation:

* Mojżesz Presburger; Dale Jabcquette, _On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation_, History and Philosophy of Logic, 1464-5149, Volume **12**, Issue 2, 1991, Pages 225 – 233 https://doi.org/10.1080/014453409108837187

The pdf [here][1] which is mentioned in Jason Dyer's comment to the original question states that in the paper above the system is used to prove its own consistency.

He reduced all statements in his arithmetic to quantifier free statements. To do this he add to extend the system by introducing modular equivalence. The result was a reduction of every statement to the quantifier free form. This led to an algorithm for deciding every statement. There is in fact bounds on the efficiency of the decision algorithm algorithm. It is greater than double exponential and less than triple exponential. For the lower bound see:

* M. J. Fischer, M. O. Rabin. _Super-Exponential Complexity of Presburger Arithmetic_, "Proceedings of the SIAM-AMS Symposium in Applied Mathematics", 1974, vol. 7, pp.27-41 https://doi.org/10.1007/978-3-7091-9459-1_5

For the upper bound see:

* Derek C. Oppen: _A $2^{2^{2^{pn}}}$ Upper Bound on the Complexity of Presburger Arithmetic_, J. Comput. Syst. Sci. 16(3): 323-332 (1978) https://doi.org/10.1016/0022-0000(78)90021-1 ([OA pdf copy](https://core.ac.uk/download/pdf/82647111.pdf))

For there to be inconsistency there would have to be a finite set of inconsistent modular statements. Because of this it is plausible to me that the original paper used the extended system to prove its own consistency. 


  [1]: http://staff.science.uva.nl/~suckelma/teaching/CL2008/2008-CL-L12.pdf