Faits: A. A.a. Sur réquisition du 19 décembre 2011 de B._ SA, l'Office des poursuites de Genève a établi à l'encontre de A._, à l'adresse " ... Londres ", un commandement de payer (poursuite n o 1) la somme de 773'749'000 fr. avec intérêts et frais, en validation du séquestre n o 2. Le commandement de payer mentionnait que, d'une part, était également notifié avec cet acte, le procès-verbal n o 2 du 19 octobre 2011 exécutant le séquestre ordonné ce même 19 octobre 2011 par le Tribunal de première instance dans la cause C/22156/2011 et que, d'autre part, le délai d'opposition à la poursuite était de 20 jours, le délai de paiement du montant poursuivi, de 30 jours, et le délai d'opposition à l'ordonnance de séquestre de 20 jours. Sur requête de l'office, cet acte a été notifié par les autorités compétentes britanniques le 1 er mars 2012, à l'adresse londonienne de A._ qui y était indiquée, par dépôt dans la boîte aux lettres de ce dernier. Conformément à l'attestation établie le 6 mars 2012 par ces mêmes autorités et versée au dossier par le débiteur poursuivi lui-même, il s'agissait là du mode de notification valable à Londres en application de l'art. 6.3 (1) (c) du Civil Procedure Rules of England and Wales. A.b. Antérieurement et ultérieurement à la notification de ce commandement de payer genevois, et du fait que des biens appartenant à A._ avaient également été séquestrés à Bâle et Zurich dans le cadre de l'ordonnance de séquestre genevoise du 19 octobre 2011, les Offices des poursuites de ces deux cantons ont fait notifier en mains du conseil londonien de A._, pour le premier, une poursuite et, pour le second, trois poursuites en validation des séquestres précités. Par quatre courriers de son conseil genevois, datés respectivement des 7, 13 et 15 mars ainsi que du 18 avril 2012, A._ s'est opposé à ces poursuites. A.c. A._ n'ayant pas formé opposition au commandement de payer genevois dans les 20 jours à compter du 1 er mars 2012, date du dépôt de cet acte dans sa boîte aux lettres de Londres, B._ SA a requis, le 10 avril 2012, la continuation de la poursuite. A.d. B._ SA a par ailleurs interjeté recours à la Cour de justice contre la décision du Tribunal de première instance du 11 septembre 2012 d'admettre l'opposition du 10 mars 2012 de A._ à l'ordonnance de séquestre du 19 octobre 2011. La procédure est toujours pendante. B. Dans l'intervalle, par lettre du 25 avril 2012, A._ avait déclaré s'opposer au commandement de payer genevois. Le 26 avril 2012, l'Office des poursuites de Genève a refusé de tenir compte de cette opposition, motif pris qu'elle était tardive. Il a considéré que le délai d'opposition, prolongé à 20 jours s'agissant d'un débiteur hors du territoire suisse, était arrivé à échéance le 21 mars 2012. Statuant le 8 novembre 2012, la Cour de justice du canton de Genève, en sa qualité de Chambre de surveillance des Offices des poursuites et faillites a, principalement, rejeté la plainte de A._ interjetée le 30 avril 2012 contre cette décision et, subsidiairement, déclaré irrecevable la requête, du même jour, en restitution du délai pour former opposition. C. Par écriture du 19 novembre 2012, A._ exerce un recours en matière civile au Tribunal fédéral. A titre principal, il conclut, prioritairement, à ce qu'il soit dit qu'il a formé opposition au commandement de payer (poursuite n o 1) et à ce que l'office soit invité à enregistrer cette opposition et à rejeter la réquisition de l'intimée du 5 avril 2012 de continuer la poursuite et, secondairement, à ce que le délai pour faire opposition lui soit restitué, qu'il soit pris acte de l'opposition du 25 avril 2012 et que l'office soit invité à enregistrer cette dernière et à rejeter la réquisition de continuer la poursuite. A titre subsidiaire, il demande l'annulation de l'arrêt attaqué et le renvoi de la cause pour nouvelle décision dans le sens des considérants et, dans tous les cas, le déboutement de l'intimée, de l'office des poursuites et de tout opposant de toutes autres ou contraires conclusions, le tout sous suite de dépens. Il n'a pas été demandé de réponses au fond. D. Par ordonnance du 5 décembre 2012, la Présidente de la II e Cour de droit civil a admis la requête de mesures provisionnelles du recourant, en ce sens qu'elle a ordonné à l'Office des poursuites du canton de Genève de surseoir à la continuation de la poursuite n o 1 jusqu'à droit connu sur le présent recours. 