This paper proposes a new type of multi-agent mobile negotiation support system named MAM-NSS in which both buyers and sellers are seeking for 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 system capable of suggesting timely and relevant action strategies for both buyers and sellers. To fulfill research purpose like this, two AI methods such as CBR (case-based reasoning) and FCM (fuzzy cognitive map) are integrated, and named MAM-NSS. 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 interrelated 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 its vacant seats to potential customers (buyers) walking around within reasonable distance. For experimental design and implementation, a multi-agent environment Netlogo is adopted. Simulation reveals that the proposed MAM-NSS could produce more robust and promising results that fit the characteristics of m-commerce.