Faits : A. Dès la fin de l'année 2008, B._ a été, en qualité de représentant de l'actionnaire unique, président du conseil d'administration de la compagnie d'assurance-vie C.Y._ SA, dont la direction générale était assurée par D._. C.Y._ SA a été déclarée en faillite le 15 décembre 2014. A la suite d'une dénonciation de la FINMA et d'une plainte de C.X._ SA en liquidation, le Ministère public a ouvert une procédure pénale contre B._ et D._, qui ont été mis en prévention pour gestion déloyale avec dessein d'enrichissement illégitime. Le 1er octobre 2015, B._ a mandaté l'avocat A._ pour la défense de ses intérêts, aux côtés de l'avocat F._, constitué le 29 avril 2015. Les deux conseils ont assisté leur client lors des audiences qui se sont déroulées devant le Ministère public les 7, 14 et 28 octobre 2015. Lors de l'audience du 7 octobre 2015, le représentant de C.X._ SA en liquidation a relevé que A._ avait été l'avocat de la société par le passé et a estimé qu'il en résultait un potentiel conflit d'intérêts. B. Par décision du 3 novembre 2015, le Ministère public a fait interdiction à A._ de représenter B._ dans la procédure en cours, ce avec effet immédiat. Statuant sur recours de A._, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a confirmé cette décision par arrêt du 17 mai 2016. C. A._ et B._ recourent contre cette décision auprès du Tribunal fédéral. Ils demandent l'annulation de l'arrêt attaqué et à ce qu'il soit dit que A._ peut assister B._ dans la procédure précitée. Le Ministère public et le Tribunal cantonal se réfèrent à leurs décisions respectives. C.X._ SA en liquidation conclut au rejet du recours. Les recourants ne répliquent pas.