Faits:
A.
Par ordonnance pénale du 11 juillet 2013, le Ministère public de la République et canton de Genève (ci-après: le Ministère public) a reconnu X._ coupable de lésions corporelles simples.
Le 29 novembre 2013, X._ a formé opposition contre l'ordonnance pénale, l'acte valant au surplus demande de restitution de délai.
Par ordonnance du 11 décembre 2013, le Ministère public a refusé de restituer le délai d'opposition, maintenu l'ordonnance pénale précitée et transmis la procédure au Tribunal de police afin qu'il statue sur la validité de l'ordonnance pénale et de l'opposition (art. 356 al. 1 CPP).
B.
Par arrêt du 14 février 2014, la Chambre pénale de recours de la Cour de justice de la République et canton de Genève a rejeté le recours de X._ tendant à la restitution du délai d'opposition et au constat que l'opposition était recevable, et a confirmé l'ordonnance du 11 décembre 2013.
L'état de fait retenu par la cour cantonale est le suivant.
A la suite d'une altercation survenue le 17 novembre 2012, Y._ a déposé plainte pénale contre X._ pour lésions corporelles simples, le 13 décembre 2012. Entendu par la police le 8 janvier 2013 en qualité de prévenu, X._ a, à son tour, déposé plainte pénale contre Y._ au même motif. A cette occasion, il a communiqué à la police son numéro de portable ainsi que deux adresses de résidence, l'une "principale", à A._ et l'autre "temporaire", à B._.
Par pli recommandé du 16 juillet 2013, le Ministère public a envoyé à X._, à son adresse principale de A._, l'ordonnance pénale prononcée le 11 juillet 2013 à son encontre. Celle-ci a été retournée au Ministère public le 18 juillet 2013 avec la mention "introuvable à l'adresse indiquée". Par publication dans la Feuille d'avis officielle le 26 juillet 2013, un délai de 10 jours a été imparti au prévenu pour retirer l'ordonnance pénale.
Par pli séparé du 16 juillet 2013, le Ministère public a expédié, en courrier B, à l'adresse principale de X._ à A._, un exemplaire de l'ordonnance pénale prononcée le 11 juillet 2013 à l'encontre de Y._. Ce courrier a été acheminé par la Poste à la nouvelle adresse de X._ à C._.
Ensuite de l'opposition formée par Y._ à l'ordonnance pénale rendue à son encontre, le Ministère public a convoqué X._, par appel téléphonique du 12 novembre 2013, en qualité de partie plaignante, à une audience fixée au 20 novembre 2013. A l'occasion de cette audience, X._ a pris connaissance de l'ordonnance pénale rendue à son encontre le 11 juillet 2013. A l'appui de l'opposition formée contre l'ordonnance pénale précitée, le recourant a expliqué avoir déménagé à C._ le 1er juillet 2013 et avoir fait le nécessaire auprès de la Poste afin de faire suivre son courrier. Selon lui, une erreur avait manifestement été commise par la Poste, sans que cela ne lui soit imputable.
C.
X._ forme un recours en matière pénale contre la décision cantonale et conclut, avec suite de frais et dépens, à sa réforme, en ce sens que la restitution du délai d'opposition contre l'ordonnance pénale du 11 juillet 2013 soit acceptée, que l'opposition du 29 novembre 2013 soit déclarée recevable et que la procédure soit transmise au Tribunal de police afin qu'il statue sur la validité de l'ordonnance pénale. Subsidiairement, il conclut à l'annulation de l'arrêt du 14 février 2014 et à ce que la cause soit renvoyée à l'autorité cantonale pour nouvelle décision dans le sens des considérants.
Invités à déposer des observations sur le recours, la cour cantonale y a renoncé, se référant aux considérants de son arrêt, alors que le Ministère public a conclu à son rejet.

Considérant en droit:
1.
Invoquant l'arbitraire dans l'établissement des faits et la violation du droit fédéral, le recourant conteste, d'une part, le refus de lui restituer le délai pour former opposition à l'ordonnance pénale du 11 juillet 2013 (art. 94 CPP) et, d'autre part, la validité de la notification effectuée par la publication du 26 juillet 2013 (art. 88 CPP).
1.1. Dans la mesure où le délai d'opposition à l'ordonnance pénale commence à courir le jour qui suit sa notification (cf. art. 90 al. 1 CPP), l'examen de la régularité de cette dernière doit intervenir préalablement à celui des conditions de restitution du délai d'opposition (art. 94 CPP).
1.2. Les autorités pénales notifient leurs prononcés par lettre signature ou par tout autre mode de communication impliquant un accusé de réception, notamment par l'entremise de la police (art. 85 al. 2 CPP).
L'art. 88 al. 1 CPP permet la notification édictale notamment lorsque le lieu de séjour du destinataire est inconnu et n'a pas pu être déterminé en dépit des recherches qui peuvent raisonnablement être exigées (let. a) et lorsqu'une notification est impossible ou ne serait possible que moyennant des démarches disproportionnées (let. b). Dans ce cas, la notification est réputée avoir eu lieu le jour de sa publication (art. 88 al. 2 CPP).
Parmi les recherches que l'on peut raisonnablement exiger avant de procéder à une notification par voie de publication dans la Feuille officielle au sens de l'art. 88 al. 1 let. a CPP, comptent notamment la prise de renseignements auprès des autorités de contrôle des habitants, des autorités militaires et de l'office postal du dernier domicile connu. Le cas échéant, une seconde tentative de notification, par l'entremise de la police, peut être exigée (cf. arrêts 6B_876/2013 du 6 mars 2014 consid. 2.3.2; 6B_652/2013 du 26 novembre 2013 consid. 1.4.3 et les références citées).
Pour qu'une notification soit impossible ou disproportionnée au sens de l'art. 88 al. 1 let. b CPP, il faut que le destinataire soit injoignable et introuvable ( SARARARD ARQUINT, in Basler Kommentar, Schweizerische Strafprozessordnung, 2011, n° 5 ad art. 88 CPP), par exemple en se soustrayant systématiquement aux tentatives de notification ( MACALUSO/TOFFEL, in Commentaire romand, Code de procédure pénale suisse, 2011, n° 13 ad art. 88 CPP).
Selon la jurisprudence, le fardeau de la preuve de la notification incombe en principe à l'autorité qui entend en tirer une conséquence juridique (<ref-ruling> consid. 2.2 p. 10; arrêts 6B_876/2013 du 6 mars 2014 consid. 2.3.2; 6B_652/2013 du 26 novembre 2013 consid. 1.4.3).
1.3. Relevant notamment que le recourant n'avait pas communiqué son changement d'adresse (de A._ à C._) au Ministère public alors même qu'il savait qu'une procédure pénale était ouverte à son encontre et qu'il devait s'attendre à recevoir une décision dans le cadre de cette procédure, la cour cantonale a implicitement reconnu que l'ordonnance pénale avait été valablement notifiée par la publication dans la Feuille officielle. Elle a par ailleurs considéré que le recourant était tenu de se renseigner auprès des autorités genevoises s'agissant de sa condamnation, dès lors qu'il avait été informé de la suite donnée à sa propre plainte, par pli simple.
1.4. Cette approche ne saurait être suivie. En effet, saisie d'un recours contre le refus du Ministère public de restituer le délai d'opposition (cf. art. 94 CPP), l'autorité cantonale devait déterminer si le recourant avait fait défaut en n'accomplissant pas un acte de procédure à temps (art. 93 CPP). Pour ce faire, elle devait, à titre préjudiciel, examiner si l'acte de procédure déterminant, en l'espèce l'opposition, avait été formé à temps, soit dans le délai de 10 jours dès la notification de l'ordonnance pénale (cf. art. 354 al. 1 CPP). Il n'y aurait défaut, que si la notification par voie de publication était valable (cf. art. 88 CPP).
Or, si l'autorité cantonale a posé les bases légales topiques (art. 85 al. 2, 87 al. 1, 93, 354 al. 1, 94 al. 1 et 88 al. 1 let. a CPP), elle a toutefois omis d'examiner si les conditions d'une notification par voie édictale étaient réalisées en l'espèce (art. 88 al. 1 CPP). Partant du principe que cette dernière était valable, elle a perdu de vue que le fardeau de la notification incombait à l'autorité concernée (cf. supra consid. 1.2), soit au Ministère public, et a ainsi exclusivement axé son raisonnement sur la restitution du délai sous l'angle de la faute du recourant.
Pourtant, il ne ressort pas de l'état de fait retenu par l'autorité cantonale que le Ministère public aurait entrepris une quelconque démarche pour tenter de localiser le recourant malgré la réception de l'ordonnance pénale litigieuse en retour avec la mention "introuvable à l'adresse indiquée". En particulier, il n'apparaît pas qu'une recherche ait eu lieu auprès du contrôle des habitants ni de l'office de Poste du dernier domicile connu du recourant, ce alors même qu'un courrier envoyé le même jour par pli simple a été acheminé à sa nouvelle adresse par ce même office. Il n'apparaît pas davantage qu'un contact téléphonique ait été entrepris avec le recourant pour se renseigner à ce sujet, malgré la mention de son numéro de portable au dossier. A cet égard, il ressort de l'état de fait cantonal que le recourant était atteignable téléphoniquement puisque c'est par ce biais qu'il a été convoqué à l'audience du 20 novembre 2013 en qualité de partie plaignante. Enfin, il ne ressort pas de l'état de fait cantonal que l'ordonnance pénale litigieuse aurait été expédiée à l'adresse "temporaire" du recourant à B._, pourtant communiquée lors de son audition par la police.
Il résulte de ce qui précède que les recherches raisonnablement exigibles au sens de l'art. 88 al. 1 let. a et b CPP n'ont pas été entreprises avant la publication dans la Feuille officielle, de sorte que cette dernière ne valait pas notification. Cela étant, le délai pour former opposition n'a pas commencé à courir le jour de la publication (cf. art. 88 al. 2 CPP), ce qui rend sans objet la question de la restitution du délai au sens de l'art. 94 CPP.
Dans la mesure où, ainsi que le retient la cour cantonale, le recourant a été informé de l'existence et du contenu de l'ordonnance pénale prononcée à son encontre lors de l'audience du 20 novembre 2013, l'opposition formée le 29 novembre 2013, est intervenue dans le délai légal de 10 jours fixé à l'art. 354 al. 1 CPP.
Par conséquent, c'est à tort que l'opposition a été jugée tardive.
2.
Au vu de ce qui précède, le recours doit être admis, sans qu'il soit nécessaire d'examiner les autres griefs soulevés par le recourant.
La décision attaquée doit être annulée et la cause doit être renvoyée au Ministère public en application de l'art. 107 al. 2 2 ème phrase LTF, afin qu'il soit donné suite à la procédure d'opposition conformément aux art. 355 ss CPP (cf. arrêts 6B_149/2013 du 27 août 2013 consid. 2; 1B_504/2012 du 11 mars 2013 consid. 4.3). Simultanément, la cause est renvoyée à la cour cantonale pour nouvelle décision sur les frais et dépens (cf. <ref-ruling> consid. 4 p. 80; arrêt 6B_552/2013 du 9 janvier 2014 consid. 3).
Le recourant obtient gain de cause. Il ne supporte pas de frais (art. 66 al. 1 et 4 LTF). Il peut prétendre à une indemnité de dépens à la charge du canton de Genève (art. 68 al. 1 et 2 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause renvoyée au Ministère public de la République et canton de Genève pour reprise de la procédure et à la cour cantonale pour nouvelle décision sur les frais et dépens de la procédure antérieure.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Genève versera au recourant une indemnité de 3'000 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 6 juin 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Boëton