In this paper, conceptual foundations, the architecture, and the implementation of an agent-based electronic marketplace, FuzzyMAN (Fuzzy Multi-Agent Negotiations) are presented. Software agents on that marketplace negotiate about multiple issues according to a multilateral negotiation protocol. This protocol is based on a sequence of bilateral negotiations and on a pre-selection procedure which chooses suitable partners for negotiations first. Special attention is given to the feature that the agents’ preferences are expressed in fuzzy terms. The application domain for our exemplary implementation is buying and selling “labor”. Agents act on behalf of employers (looking for employees) and employees (looking for jobs). A mediator agent in FuzzyMAN supervises and coordinates the actions on the marketplace. Characteristics of the architecture and its implementation are described. Open research questions are discussed in the final section.