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.

Considérant en droit:
1. 1.1 Interjeté par la partie qui a succombé dans ses conclusions en paiement et qui a donc qualité pour recourir (<ref-law>), dirigé contre un arrêt final (<ref-law>) rendu en matière civile (<ref-law>) par une autorité cantonale de dernière instance statuant sur recours (<ref-law>) dans une affaire pécuniaire dont la valeur litigieuse atteint le seuil de 30'000 fr. (<ref-law>), le recours est en principe recevable, puisqu'il a été déposé dans le délai (<ref-law>) et la forme (<ref-law>) prévus par la loi.
1.2 Le recours peut être interjeté pour violation du droit, tel qu'il est délimité par les art. 95 et 96 LTF. Il peut donc être formé pour violation d'un droit constitutionnel (<ref-ruling> consid. 2.1 p. 247; <ref-ruling> consid. 2.4 p. 313).
Le Tribunal fédéral applique le droit d'office (<ref-law>). Il n'est donc limité ni par les arguments soulevés dans le recours, ni par la motivation retenue par l'autorité précédente; il peut admettre un recours pour un autre motif que ceux qui ont été invoqués et il peut rejeter un recours en adoptant une argumentation différente de celle de l'autorité précédente (<ref-ruling> consid. 1.4 et l'arrêt cité). Compte tenu de l'exigence de motivation contenue à l'art. 42 al. 1 et 2 LTF, sous peine d'irrecevabilité (<ref-law>), le Tribunal fédéral n'examine en principe que les griefs invoqués. Il n'est pas tenu de traiter, comme le ferait une autorité de première instance, toutes les questions juridiques qui se posent lorsque celles-ci ne sont plus discutées devant lui (<ref-ruling> consid. 2.2.1 p. 389; <ref-ruling> consid. 1.4 p. 400). Par exception à la règle selon laquelle il applique le droit d'office, il ne peut entrer en matière sur la violation d'un droit constitutionnel ou sur une question relevant du droit cantonal ou intercantonal que si le grief a été invoqué et motivé de manière précise par la partie recourante (<ref-law>).
1.3 Le Tribunal fédéral conduit son raisonnement juridique sur la base des faits établis par l'autorité précédente (<ref-law>). Il ne peut s'en écarter que si les faits ont été établis de façon manifestement inexacte - ce qui correspond à l'arbitraire au sens de l'art. 9 Cst. (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 2.4) - ou en violation du droit au sens de l'<ref-law> (<ref-law>).
La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées, faute de quoi il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée (<ref-ruling> consid. 1.2 p. 187; <ref-ruling> consid. 1.4 et 6.2). Une rectification de l'état de fait ne peut être demandée que si elle est de nature à influer sur le sort de la cause (<ref-law>). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (<ref-law>).
1.4 Le Tribunal fédéral ne peut aller au-delà des conclusions des parties (<ref-law>). Toute conclusion nouvelle est irrecevable (<ref-law>).
2. 2.1 Le recourant ayant son domicile à l'étranger, la cause revêt un caractère international, de sorte que la question du droit applicable doit être examinée d'office par le Tribunal fédéral (ATF 4A_325/2011 du 11 octobre 2011 consid. 2.1; <ref-ruling> consid. 3.2 p. 144 et les arrêts cités).
La question doit être tranchée selon le droit international privé du for, soit in casu la loi fédérale sur le droit international privé du 18 décembre 1987 (LDIP, RS 291; ATF 4A_325/2011 du 11 octobre 2011 consid. 2.1; <ref-ruling> consid. 2.1 p. 261) et la qualification du rapport juridique litigieux doit être effectuée selon le droit interne du for (ATF <ref-ruling> consid. 3.2 p. 144; <ref-ruling> consid. 4 p. 615).
Le recourant invoque des faits qui pourraient conduire à admettre l'existence d'un mandat (<ref-law>) ou d'un dépôt (<ref-law>). Dans les deux cas, en l'absence d'une professio juris, le droit applicable est celui de la résidence habituelle ou de l'établissement de la partie qui fournit la prestation caractéristique, soit en l'espèce la société intimée qui a son siège à Genève (art. 117 al. 1, 2 et 3 let. c et d LDIP).
Le droit suisse est donc applicable.
2.2 Selon l'<ref-law>, chaque partie doit, si la loi ne prescrit le contraire, prouver les faits qu'elle allègue pour en déduire son droit.
En l'absence d'une disposition spéciale instituant une présomption, l'<ref-law> répartit le fardeau de la preuve pour toutes les prétentions fondées sur le droit fédéral et détermine, sur cette base, laquelle des parties doit assumer les conséquences de l'échec de la preuve (<ref-ruling> consid. 3.1; <ref-ruling> consid. 2.6). Il en résulte que la partie demanderesse doit prouver les faits qui fondent sa prétention, tandis que sa partie adverse doit prouver les faits qui entraînent l'extinction ou la perte du droit (<ref-ruling> consid. 3.1 p. 323). L'<ref-law> ne prescrit cependant pas comment les preuves doivent être appréciées et sur quelles bases le juge peut forger sa conviction (<ref-ruling> consid. 2d; <ref-ruling> consid. 3a).
En l'espèce, il incombait donc au recourant, en sa qualité de partie demanderesse, de prouver les faits qu'il alléguait pour établir l'existence de sa prétention. Ses conclusions ayant été réduites à des conclusions en paiement, il devait prouver qu'il avait remis des fonds à la société intimée dans des circonstances telles que celle-ci devait les lui restituer. Si ce point de fait décisif reste douteux, l'action en restitution doit être rejetée en application de l'<ref-law>.
En conséquence, il n'appartenait pas à la société intimée de prouver qu'elle n'avait rien reçu, mais au demandeur d'établir qu'il avait versé des fonds à la société.
La question de savoir comment les preuves doivent être appréciées, ainsi qu'on vient de le voir, n'est pas régie par l'<ref-law>.
2.3 L'appréciation des preuves relève de l'établissement des faits, qui (cf. consid. 1.3 ci-dessus) ne peut être réexaminé par le Tribunal fédéral que dans les limites tracées par l'<ref-law>.
Le recourant soutient que les preuves ont été appréciées de manière arbitraire, c'est-à-dire en violation de l'art. 9 Cst. S'agissant d'un grief de nature constitutionnelle, il appartient au recourant de démontrer l'arbitraire par une argumentation répondant aux exigences de l'<ref-law> (<ref-ruling> consid. 4.1.2 p. 62; <ref-ruling> consid. 1.4.3 p. 254 s.).
Selon la jurisprudence, l'arbitraire, prohibé par l'art. 9 Cst., ne résulte pas du seul fait qu'une autre solution pourrait entrer en considération ou même qu'elle serait préférable; le Tribunal fédéral n'annulera la décision attaquée que lorsque celle-ci est manifestement insoutenable, qu'elle se trouve en contradiction claire avec la situation de fait, qu'elle viole gravement une norme ou un principe juridiques indiscutés, ou encore lorsqu'elle heurte de manière choquante le sentiment de la justice et de l'équité. Pour qu'une décision soit annulée pour cause d'arbitraire, il ne suffit pas que la motivation formulée soit insoutenable, il faut encore que la décision apparaisse arbitraire dans son résultat (<ref-ruling> consid. 2.4 p. 5; <ref-ruling> consid. 2.2.2 p. 318/319; <ref-ruling> consid. 4.2 p. 560).
S'agissant plus précisément de l'appréciation des preuves, la décision n'est arbitraire que si le juge n'a manifestement pas compris le sens et la portée d'un moyen de preuve, s'il a omis, sans raison sérieuse, de tenir compte d'un moyen important propre à modifier la décision attaquée ou encore si, sur la base des éléments recueillis, il a fait une déduction insoutenable (ATF <ref-ruling> consid. 4.2 p. 560; <ref-ruling> consid. 2.1 p. 9).
2.4 Le recourant a soutenu qu'il avait signé un contrat de gestion de fortune avec la société intimée. Si tel avait été le cas, il en aurait nécessairement reçu une copie qu'il aurait été en mesure de produire dans la procédure, puisqu'il a pu produire des documents antérieurs. Certes, deux témoins ont affirmé que ce contrat existait, mais leur crédibilité est douteuse pour des raisons qui seront examinées ultérieurement, de sorte que ces deux déclarations ne sont pas suffisantes pour lever le doute. A cela s'ajoute un autre argument: un gérant de fortunes indépendant agit pour ses clients au moyen d'un compte bancaire. Les deux témoins déjà évoqués ont déclaré que le recourant avait ouvert un compte à la banque Y._. Aucune pièce n'a cependant pu être produite pour démontrer l'existence de ce compte et les parties ont finalement admis qu'il n'existait pas. On ne voit dès lors pas avec quel compte (du client ou de la société) l'intimée aurait opéré pour gérer la fortune confiée par le recourant. Dans ce contexte, il n'apparaît pas que la cour cantonale ait statué arbitrairement en considérant que l'existence d'un contrat de gestion de fortune était douteuse.
Que la nouvelle société ait souhaité reprendre la clientèle de la précédente ne signifie pas encore que le recourant ait accepté de conclure avec la nouvelle société. La révocation des pouvoirs accordés à l'ancienne société marque plutôt une rupture et on ne discerne aucune manifestation de volonté du recourant en faveur de la conclusion d'un contrat avec la nouvelle société.
De toute manière, la question pertinente au stade initial du raisonnement n'est pas de savoir si les parties ont ou non conclu un contrat et, dans l'affirmative, si ce contrat doit être qualifié de mandat ou de dépôt. La première question est de savoir si le recourant a confié des fonds à l'intimée. En effet, si cette question de fait doit recevoir une réponse négative, il importe peu de savoir s'il y a eu ou non un contrat entre les parties et quelle en est la nature, puisque l'intimée ne saurait être tenue de restituer ce qu'elle n'a jamais reçu.
Pour tenter de justifier sa prétention, le recourant se fonde sur le document établi le 15 octobre 2001. Comme il a été allégué que celui-ci était un acte de complaisance ne correspondant pas à la vérité, la cour cantonale se devait d'examiner la question. On observe tout d'abord que ce document indique que les fonds sont placés auprès de la banque Y._. Cependant, il a été admis que le recourant n'avait pas de compte à la banque Y._. Par ailleurs, le recourant a été dans l'incapacité de prouver l'origine des fonds mentionnés dans cette attestation. Il a certes établi deux versements sur le compte de l'épouse de B._ - ce qui est déjà singulier - mais, compte tenu des virements effectués ensuite en faveur du recourant, on ne parvient en tout cas pas aux chiffres indiqués dans le document litigieux.
Pour justifier néanmoins ces montants, le recourant allègue qu'il a effectué des versements en espèces. Les deux témoins déjà cités ont confirmé qu'ils avaient assisté à des versements en espèces, mais en précisant qu'une assistante administrative de la société avait toujours participé aux encaissements. Or, cette assistante administrative, entendue comme témoin, a formellement contesté ces versements. A cela s'ajoute qu'il est invraisemblable, compte tenu des usages commerciaux, qu'une personne remette des sommes importantes à un employé sans exiger la remise immédiate d'un reçu. Le recourant n'a pas été en mesure de produire le moindre reçu concernant les prétendus versements en espèces. En concluant que leur existence était douteuse, la cour cantonale n'a pas apprécié les preuves de manière insoutenable.
Ainsi, le document litigieux du 15 octobre 2001 apparaît douteux non seulement parce qu'il parle, au sujet du recourant, de " son compte " et de la banque Y._ alors que le recourant n'a pas eu de compte dans cet établissement bancaire, mais aussi parce que les chiffres articulés apparaissent invraisemblables au vu des preuves apportées. En considérant que ce document contesté n'avait pas une force probante suffisante pour démontrer l'existence de la créance, la cour cantonale n'a en rien versé dans l'arbitraire.
Le recourant, pour établir sa prétention, s'est fondé aussi largement sur les dépositions des deux témoins déjà maintes fois cités. La cour cantonale a constaté - sans que l'arbitraire ne soit invoqué à ce sujet - que l'un d'eux avait eu un conflit de droit du travail avec la société intimée, ce qui impliquait que ses déclarations soient accueillies avec circonspection. Les deux témoins ont exposé que le recourant avait ouvert un compte à la banque Y._, ce qui s'est révélé faux, comme les deux parties l'ont admis. Sur les montants, ils se sont montrés plutôt vagues. Ils ont affirmé qu'ils avaient assisté à la remise de fonds en espèces, en présence de l'assistante administrative, alors que celle-ci, entendue comme témoin, a catégoriquement contesté ces faits. Ils ont aussi affirmé avoir vu un contrat de gestion écrit, alors que le recourant a été dans l'incapacité de produire la copie de ce document. Il apparaît ainsi que les déclarations de ces deux témoins, sur de nombreux points, sont douteuses. Dès lors, la cour cantonale n'a pas statué arbitrairement en considérant que ces dépositions n'étaient pas suffisamment crédibles pour emporter la conviction.
Il est certes établi que le recourant était ami de B._ et que, après le retrait de la licence de la précédente société, des fonds appartenant au recourant ont été versés sur le compte de l'épouse du prénommé, fonds qui ont ensuite donné lieu à divers virements en faveur du recourant. Ces opérations ne permettent pas d'établir un lien avec la société intimée. Il n'est en tout cas pas prouvé que le recourant, par ces opérations, ait remis et confié des fonds à la société intimée.
Les preuves n'ont ainsi pas été appréciées arbitrairement et l'argumentation du recourant ne parvient pas à démontrer le contraire.
2.5 A considérer ce résultat, le Tribunal fédéral est lié par les constatations cantonales (<ref-law>). Or il ne ressort pas des constatations cantonales que la société intimée ait reçu des fonds dont elle puisse être redevable. En conséquence, la demande a été rejetée sans violer le droit fédéral.
L'argumentation juridique figurant à la fin du recours repose sur un état de fait qui n'est pas celui retenu par la cour cantonale, de sorte qu'il n'y a pas lieu d'entrer en matière à son sujet.
3. Les frais judiciaires et les dépens sont mis à la charge de la partie qui succombe (art. 66 al. 1 et 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 8'500 fr., sont mis à la charge du recourant.
3. Le recourant versera à l'intimée une indemnité de 9'500 fr. à titre de dépens.
4. Le présent arrêt est communiqué aux mandataires des parties et à la Cour de justice du canton de Genève, Chambre civile.
Lausanne, le 30 novembre 2011
Au nom de la Ire Cour de droit civil
du Tribunal fédéral suisse
La Présidente: Klett
Le Greffier: Ramelet