Modern networked business environment enables design of flexible and effective mechanisms of exchange between economic parties. Online negotiations allow geographically and temporally separated participants to engage in exchange of offers in search for acceptable agreements. The digital medium enables development of software agents, which can assist with negotiation tasks while saving time and human effort. The current paper investigates the prospects of utilizing software agents in negotiations with the human counterparts. It presents the findings from experiment where human subjects acted as buyers negotiating with software agent sellers over a mobile phone plan. An electronic negotiation system incorporating software agents was used in the experiment. The agents employed various concession-making schedules while engaging in negotiation tasks involving one of two complexity levels. Negotiation task complexity was manipulated using different number of issues involved in the negotiations. Subjects were recruited among university students. Negotiations between the subjects and agents took place during a two-day period in an asynchronous mode through the web. The findings suggest that interaction between negotiation task complexity and negotiation tactic has significant effects on negotiation outcomes and subjective assessments by the human participants. In particular, task complexity had a higher impact on the agreement rate when agents employed a competitive tactic vs. when they used a conceding one.