Faits: A. Le 6 mars 2012, A._, B._, C._ et D._ (ci-après: les plaignants) ont déposé plainte pénale pour escroquerie et faux dans les titres contre X._, respectivement leur fille et leur soeur. Ils reprochent à la prénommée de les avoir trompés et de s'être attribué illégitimement le 40% des actifs appartenant à Y._, respectivement leur mari et leur père, décédé en mars 2010. Ils l'accusent aussi d'avoir créé un titre faux visant à démontrer qu'ils renonçaient à leur parts dans la société Z._, société titulaire de comptes, sur lesquels Y._ possédait des avoirs à concurrence d'environ aaa euros. Dans le cadre de cette instruction pénale, le Ministère public du canton de Genève (ci-après: le Ministère public) a ordonné, le 24 septembre 2012, la saisie des comptes "xxx" et "zzz" détenus par X._ auprès de la Banque L._ SA. X._ avait ouvert un compte, le 13 mars 2011, auprès de la banque M._ SA, sur lequel elle avait versé bbb euros, montant correspondant à sa part successorale. Le 7 juillet 2011, un montant de ccc francs avait été débité dudit compte et versé à l'intention du conseil de la prénommée. A la mi-décembre 2011, X._ avait clôturé ledit compte et avait transféré la totalité de ses avoirs sur le compte "xxx" auprès de la Banque L._ SA, étant précisé que les avoirs avaient transité via un compte ouvert auprès de la banque O._ SA. Elle avait déposé sur le compte "zzz" le 40% des avoirs précédemment détenus par la société Z._. Le 25 février 2013, le Ministère public a levé le séquestre frappant le compte "xxx". Il a considéré que l'argent bloqué sur ledit compte provenait de la part d'héritage de la prénommée et n'était pas visé par les infractions qui lui étaient reprochées. B. Par arrêt du 19 août 2013, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours formé par les plaignants. Elle a considéré en substance qu'il n'y avait pas de liens entre les avoirs séquestrés et l'infraction reprochée à l'intimée. C. Agissant par la voie du recours en matière pénale, A._, B._, C._ et D._ demandent principalement au Tribunal fédéral d'annuler la décision de levée de séquestre du 25 février 2013 et l'arrêt cantonal du 19 août 2013. Ils concluent subsidiairement au renvoi de la cause à la cour cantonale pour nouvelle décision. Ils demandent l'effet suspensif, qui a été accordé par ordonnance présidentielle du 23 septembre 2013. La Cour de justice se réfère à son arrêt. Le Ministère public et l'intimée concluent au rejet du recours. Les recourants ont répliqué par courrier du 24 octobre 2013. L'intimée a dupliqué le 15 novembre 2013.