This paper investigates how Multi-agents can digitally sign transactions in an untrusted environment securely. We present an agent-based scenario for e-Payment and discuss techniques using multiple agents that have been implemented to provide security in this scenario. The underlying techniques are based on existing theoretical schemes. These schemes generally have a significant overhead which is caused by the use of multiple agents. However, this overhead can be compensated by the functionality offered in our proposed scenario. The schemes require no interaction of the originator once the mobile agents are sent out. They are therefore particularly suited for situations in which a user cannot stay online for a long time. We also address some possible security threats which lead to new observations on using threshold signature schemes in the context of mobile agents.