Faits: A. A._ et B._ se sont liés d'amitié aux Etats-Unis d'Amérique en 1984. S'étant perdus de vue après leur retour en Europe, ils ont renoué contact en 1991 à l'occasion du mariage de B._. Domicilié en France et souhaitant bénéficier d'une relation bancaire à Genève afin de faciliter le mouvement de ses liquidités, A._ a ouvert, le 30 mai 1997, un compte auprès de la banque X._. Il a accordé le pouvoir de gérer ce compte à la société W._ SA, à Genève, active dans la gestion de fortune et le conseil en placements, qui avait pour président du conseil d'administration B._. Divers transferts de fonds et virements ont été opérés sur le compte. En 2000, la société W._ SA a perdu sa licence. Le 25 septembre 2000, A._ a révoqué le pouvoir qu'il lui avait accordé. La faillite de la W._ SA a été prononcée le 7 avril 2003. Le 9 octobre 2000, B._ a fondé la société K._ SA, ayant son siège à Genève et pour but les services financiers ainsi que la gestion de fortune. L'idée était de reprendre les activités qu'exerçait W._ SA. Par le débit de son compte auprès de la banque X._, A._ a transféré 130'000 USD le 15 novembre 2000 et 70'000 USD le 15 juin 2001 sur le compte auprès de la banque Y._ de l'épouse de B._, sur lequel ce dernier disposait d'une procuration. Par le débit de ce compte auprès de la banque Y._, les sommes suivantes ont été virées sur le compte de A._ auprès de la banque Z._ : 10'000 EUR le 8 mars 2001, 15'244,90 EUR le 4 septembre 2001 et 8'000 EUR le 24 décembre 2001. En outre, toujours par le débit de ce compte, 120'000 EUR le 18 décembre 2000 et 20'000 EUR le 10 mars 2003 ont été virés sur les comptes de sociétés appartenant à A._. Un document établi le 15 octobre 2001, sous la raison sociale de K._ SA, atteste que A._ est client de la société et qu'il détient actuellement sur son compte 330'000 EUR, 70'000 USD et 90'000 CHF; ces montants, échus au 30 septembre 2001, ont été replacés en dépôt à un mois auprès de la banque Y._. B._, signataire de ce texte, a déclaré finalement qu'il ne s'agissait que d'un document de complaisance. Par courrier du 31 mai 2006, A._ a sommé K._ SA de lui fournir un relevé détaillé des fonds qu'il lui avait confiés et de les lui restituer. K._ SA a répondu par courrier du 15 juin 2006 en contestant avoir jamais détenu des fonds de A._. B. Par acte déposé le 3 avril 2007 en mains du Tribunal de première instance de Genève, A._ a formé une demande en paiement dirigée contre K._ SA, réclamant à cette dernière la reddition des comptes et le paiement de 652'228 fr. 90 avec intérêts à 5 % dès le 16 octobre 2006. Soutenant qu'un mandat de gestion avait été conclu entre les parties, il fonde sa demande sur le document du 15 octobre 2001, sous déduction des transferts qu'il reconnaît. K._ SA s'est opposée à la demande en totalité, contestant toute relation contractuelle entre elle-même et le demandeur. Par jugement du 16 septembre 2010, le Tribunal de première instance a débouté A._ de toutes ses conclusions. A._ a appelé de ce jugement, concluant à la condamnation de sa partie adverse à lui payer la somme de 652'228 fr. 90 avec intérêts à 5 % dès le 16 octobre 2006. K._ SA a conclu au rejet de l'appel. Statuant sur l'appel, la Chambre civile de la Cour de justice du canton de Genève, par arrêt du 15 avril 2011, a confirmé le jugement attaqué. Procédant à une appréciation des preuves apportées, la cour cantonale est parvenue à la conclusion que le demandeur n'avait pas prouvé l'existence d'une relation contractuelle entre les parties et la remise de fonds à la société défenderesse. C. A._ exerce un recours en matière civile au Tribunal fédéral contre cet arrêt. Invoquant l'arbitraire dans l'appréciation des preuves qui aurait entraîné une violation du droit fédéral, il conclut à l'annulation de l'arrêt attaqué et à la condamnation de sa partie adverse à lui verser la somme de 652'228 fr. 90 avec intérêts à 5 % dès le 16 octobre 2006. Subsidiairement, il demande le renvoi de la cause à la cour cantonale. L'intimée propose le rejet du recours. 