Ad Hoc network is a multi-hop temporary communication network of mobile nodes. Because the lack of infrastructure support in Ad Hoc network, some attacks are more serious than in other type of networks. [1] Therefore security problem in this type of network is a challenging issue. To against the attacks which threat seriously security of Ad Hoc network, a new authentication scheme is proposed. The proposed solution involves three main stages: intermediate nodes pre-authenticating stage, common key ki between n0 and ni negotiating stage and authentication during all routing phases. At the same time, the network simulation of the proposed solution is conducted. The simulation result shows that the proposed solution effectively resists the attacks mentioned above. Meanwhile, the negative affection to the performance of network, such as delay and overheads, is tolerable according to the simulative result. The research in this paper enable us to put forward a reasonable authentication solution during all phases.