Faits : A. A.a. D._, de nationalité française, est décédé le 15 juillet 2012 à Londres. Il avait trois enfants, soit A._ et B._, issus de son premier mariage, ainsi que C._, issue d'une seconde union. En troisièmes noces, il a épousé E._ en 2011 à Londres. A.b. En 1994, D._ a quitté la France, sans y conserver d'adresse, pour le Royaume-Uni. En 1997, D._ et sa deuxième épouse ont emménagé dans une maison à Londres. Après leur divorce, il a continué à vivre dans cette maison avec E._, qui y vit actuellement. Selon ses déclarations fiscales des sept dernières années avant sa mort, D._ était imposé à Londres selon le système de " remittance basis ", soit une imposition forfaitaire sur la dépense. Il a déclaré être résident, mais non domicilié, au Royaume-Uni. A.c. D._ avait acquis une collection d'oeuvres d'art entreposée en Suisse à la société F._ SA, ainsi qu'auprès de la société G._ SA. Il détenait également en Suisse des comptes bancaires. Ses actifs sont détenus au nom de divers sociétés, trustset fondations, qu'il a constitués pour gérer son patrimoine. A.d. Par testament du 9 février 2011, D._ a désigné son épouse E._ comme étant légataire universelle de tous ses biens, notamment sa collection d'oeuvres d'art entreposée à V._ et ses avoirs bancaires. Il a également légué une somme d'argent à C._, mais pas à ses deux autres enfants. Par " letter of wishes " du 16 avril 2011, D._ a sollicité la modification de certains legs et réaffirmé que tous ses autres biens revenaient à E._. Il précisait toutefois ne pas vouloir empiéter sur le pouvoir discrétionnaire du trustee. A.e. Sur requête de A._, un notaire actif à Paris a établi le 1 er août 2012 un acte constatant la qualité d'héritier des trois enfants du défunt. Il ressort aussi de cet acte que, selon le notaire, la loi française est applicable au règlement de la succession du défunt. A.f. Se fondant notamment sur cet acte notarié, B._ a saisi le Tribunal de grande instance de Paris. Cette autorité a rendu, sans audition des parties, une ordonnance de mesures conservatoires. Celle-ci faisait notamment interdiction à E._, ainsi qu'à tout tiers détenteur de biens de la succession de D._, d'accomplir des actes d'administration et de disposition portant sur les biens appartenant aux héritiers indivis de ce dernier. B. B.a. B.a.a. Par requête déposée le 3 novembre 2014 au Tribunal de première instance de Genève (ci-après: le tribunal), A._ et B._ ont conclu à ce que le tribunal ordonne le séquestre, à concurrence de 14'652'470 fr. avec intérêts à 5% l'an dès le 15 juillet 2012, de tous les biens mobiliers, oeuvres d'art et actifs détenus par F._ SA, par G._ SA, par la banque H._ SA et K._ SA pour le compte de E._, en son propre nom ou comme ayant droit économique par le truchement de personnes physiques ou morales. Par ordonnance de séquestre n° *** du 4 novembre 2014, le tribunal a fait droit à cette requête. B.a.b. E._ a formé opposition contre cette ordonnance. Par jugement du 18 mai 2015, le tribunal a admis l'opposition au séquestre et a révoqué l'ordonnance précitée. Il a retenu que les requérants n'avaient pas rendu vraisemblable l'application du droit français à la succession de leur père et, partant, leur créance, le caractère frauduleux de la domiciliation du défunt sur sol britannique n'étant pas rendu suffisamment plausible. B.b. Par arrêt du 15 septembre 2015, la Cour de justice du canton de Genève a rejeté le recours interjeté par A._ et B._ contre ce jugement. C. Par acte posté le 16 octobre 2015, A._ et B._ interjettent un recours en matière civile contre cet arrêt devant le Tribunal fédéral. Ils concluent, principalement, à sa réforme en ce sens que l'opposition formée par E._ contre l'ordonnance du 4 novembre 2014 est rejetée, et, subsidiairement, à son annulation et au renvoi de la cause à l'autorité cantonale pour qu'elle statue dans le sens des considérants. En substance, ils se plaignent d'arbitraire dans l'application de l'art. 272 al. 1 ch. 1 LP et dans l'établissement des faits. Des observations n'ont pas été requises. D. Par ordonnance du 5 novembre 2015, la requête d'effet suspensif assortissant le recours a été admise. La requête de sûretés formulée par l'intimée a été déclarée irrecevable.