Faits: A. Le 23 avril 2013, X._ a été arrêté par la police genevoise, prenant alors connaissance de la procédure pénale ouverte à son encontre par le Ministère public de la République et canton de Genève - représenté depuis mars 2012 par le Procureur Y._ - pour fraude dans la saisie, voire diminution de l'actif au préjudice des créanciers (cause xxx). A cette même date, ont eu lieu des perquisitions à son domicile, ainsi que dans ses locaux professionnels. Par fax du 23 avril 2013, X._ a requis sa mise en liberté immédiate et demandé au Procureur Y._ de se dessaisir de la cause xxx. A l'appui de cette seconde requête, le prévenu a expliqué que le magistrat avait été avocat-stagiaire, puis collaborateur dans l'étude où travaillait Me Z._. Or, ce dernier représentait la partie plaignante dans une précédente procédure pénale intentée à son encontre, à la suite de laquelle il avait été condamné. Après avoir transmis cette requête à la Chambre pénale de recours de la C our de justice de la République et canton de Genève, le Ministère public s'y est opposé. Il a confirmé avoir effectué son stage (de septembre 2007 à septembre 2008) dans l'étude où Me Z._ avait exercé jusqu'au 1er mai 2009 et y avoir ensuite travaillé comme collaborateur, puis associé (de janvier 2009 à décembre 2011). Selon les informations figurant dans le système informatique judiciaire, la procédure pénale dans laquelle Me Z._ intervenait contre X._ avait débuté le 7 mai 2008 et s'était achevée le 15 février 2010. Le Procureur a encore précisé ne pas se souvenir si l'affaire en question avait été évoquée à l'époque. Quant aux actes d'instruction entrepris dans la procédure pénale xxx - perquisitions et arrestation du requérant -, ils étaient, selon le magistrat, justifiés par la récolte d'informations sur les comptes bancaires où se trouvaient les montants que le prévenu était soupçonné d'avoir envoyé à l'étranger et par un risque de collusion. X._ a persisté dans ses conclusions, relevant le caractère médiatisé de l'affaire pénale défendue par Me Z._. B. Le 3 juillet 2013, la Chambre pénale de recours a rejeté la requête de récusation au motif que les circonstances d'espèce (absence de participation audit dossier, départ de l'étude de Me Z._ un an avant l'achèvement de la procédure pénale et défaut d'élément concret indiquant une connaissance par le Procureur de cette affaire à l'époque) n'étaient objectivement pas suffisantes pour retenir une apparence de prévention. La cour cantonale a en outre relevé que l'aspect médiatique de cette procédure - alors close - était dénué de pertinence et que les mesures prises par le Ministère public dans la cause xxx ne constituaient pas des violations graves dénotant une intention de nuire. C. Par mémoire du 9 septembre 2013, X._ forme un recours en matière pénale, concluant à l'annulation de l'arrêt cantonal, à la récusation du Procureur et, subsidiairement, au renvoi de la cause à l'autorité cantonale pour qu'elle statue au sens des considérants. Invités à se déterminer, le Ministère public a conclu au rejet du recours, renvoyant aux observations déposées devant l'instance précédente, tandis que cette dernière s'est référée à ses considérants, sans formuler de détermination complémentaire. Le 23 octobre 2013, le recourant a persisté dans ses conclusions.