This chapter proposes a new type of multi-agent mobile negotiation support system named MAMNSS in which both buyers and sellers are seeking the best deal given limited resources. Mobile commerce, or m-commerce, is now on the verge of explosion in many countries, triggering the need to develop more effective decision support systems capable of suggesting timely and relevant action strategies for both buyers and sellers. To fulfill a research purpose like this, two artificial intelligence (AI) methods such as CBR (casebased reasoning) and FCM (fuzzy cognitive map) are integrated and named MAM-NSS. The primary advantage of the proposed approach is that those decision makers involved in m-commerce regardless of buyers and sellers can benefit from the negotiation support functions that are derived from referring to past instances via CBR and investigating inter-related factors simultaneously through FCM. To prove the validity of the proposed approach, a hypothetical m-commerce problem is developed in which theaters (sellers) seek to maximize profit by selling their vacant seats to potential customers (buyers) walking around within reasonable distance. For experimental design and implementation, a multi-agent environment Netlogo is adopted. A simulation reveals that the proposed MAM-NSS could produce more robust and promising results that fit the characteristics of m-commerce.