In this paper, the authors have devised a new robust beam forming algorithm called Variable Step Size Normalized Least Mean Square (VSSNLMS) for smart antenna systems. Firstly, the performance of Least Mean Square (LMS) and Normalized Least Mean Square (NLMS) algorithms are analyzed with respect to the convergence speed and interference suppression capability. It is found that, both the methods use fixed step size. As a result of this, they show low convergence rate. Hence these algorithms cannot track the desired signal properly in an environment, where the signal characteristics are changing rapidly. The proposed VSSNLMS algorithm uses a variable step size. This improves the convergence rate and produces deep nulls in the direction of interferences which improves the interference suppression. Hence the proposed method is robust and better than the normal LMS and NLMS algorithms and can be used effectively in advanced mobile communication applications.