Faits : A. Dans le cadre de la succession de C.X._, un litige, notamment en lien avec la propriété Y._, oppose D._, la compagne de celui-ci désignée exécutrice testamentaire pour l'un des bâtiments, à ses deux enfants et héritiers, A.X._ et B.X._. A la suite de la plainte pénale déposée par le fils et la fille X._ le 30 août 2013, le Ministère public de la République et canton de Genève a ouvert le 6 septembre 2013 une instruction contre D._ pour appropriation illégitime (art. 137 CP), vol (art. 139 CP), tentative d'extorsion et chantage (art. 22 et 156 CP), gestion déloyale (art. 158 CP), ainsi qu'insoumission à une décision d'autorité (art. 292 CP; P/zzz). Au cours de l'instruction, ont été entendus, en qualité de témoins, le majordome et le régisseur de la propriété. Les deux hommes ont en substance déclaré qu'aucun objet n'avait été déplacé du domaine depuis le décès du père des parties plaignantes. Ultérieurement et après avoir soutenu avoir subi des pressions de la part de D._, ils sont revenus sur leurs déclarations (auditions des 24 septembre et 4 novembre 2014). Une procédure pour faux témoignage a été ouverte à leur encontre et il ressort de l'enquête y relative que les deux hommes sont à l'origine du cambriolage perpétré le 23 avril 2014 au domaine Y._, durant lequel des biens pour plusieurs millions de francs suisses ont été dérobés (P/xxx, P/yyy et P/www). Le 20 janvier 2015, le Ministère public a rendu une ordonnance de non-entrée en matière sur la plainte déposée le 23 décembre 2014 par A.X._ et B.X._ à l'encontre de D._ pour entrave à l'action pénale (art. 305 CP) et instigation à faux témoignage (art. 24 et 307 CP). Le Procureur a considéré, d'une part, que le cambriolage réalisé par le majordome et le régisseur entachaient la crédibilité de leurs déclarations tendant à orienter les soupçons sur D._ et, d'autre part, qu'aucun élément ne permettait de supposer que l'associé-gérant de Z._ Sàrl - entendu le 5 novembre 2014 - aurait subi des pressions de la part de la mise en cause. B. Le 21 mai 2015, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a déclaré irrecevable le recours intenté par A.X._ et B.X._ contre cette décision dans la mesure où elle concernait l'infraction d'entrave à l'action pénale. L'autorité cantonale a ensuite rejeté le recours en relation avec le chef de prévention d'instigation à faux témoignage. C. Par acte du 22 juin 2015, A.X._ et B.X._ forment un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant à son annulation. Ils demandent à ce qu'il soit ordonné au Ministère public d'instruire leur plainte pénale du 23 décembre 2014 contre D._. A titre subsidiaire, ils requièrent le renvoi de la cause à l'autorité précédente.