Designing non-linear model predictive control (NMPC) laws for controlling multiple autonomous surface vessels in arbitrary formations in environments containing obstacles are reported in this paper. Two leader-follower decentralized geometrical control schemes that are required for defining a unique two-dimensional formation are considered. A three-degree-of-freedom dynamic model of surface vessels has been used for the controller design. It is assumed that the surface vessels are under-actuated and obstacles are present in the vessels' work environment. The real-time optimization abilities of the NMPC method has been used to improve the response of the unactuated DOF of the vessels and to directly incorporate the local obstacle avoidance into the formation control eliminating the need for an external local obstacle avoidance algorithm. This leads to more effective obstacle avoidance decisions based on the dynamics of the vehicle. The effectiveness the developed control law, even in the presence of model uncertainty and external disturbances are demonstrated via computer simulations.