Faits:
A.
Par ordonnance pénale du 23 mai 2013, le Ministère public de l'arrondissement de Lausanne a condamné A._ pour faux dans les titres, à une peine pécuniaire de 45 jours-amende à 70 fr. avec sursis pendant 2 ans et à une amende de 630 fr., la peine privative de liberté de substitution en cas de non-paiement fautif étant fixée à 9 jours. Cette décision a été notifiée par pli recommandé à l'adresse personnelle communiquée par A._ à l'autorité. Celui-ci n'a pas retiré le pli durant le délai de garde, qui a été retourné à l'autorité.
En substance, il a été reproché à A._, gérant d'immeubles, d'avoir ajouté, après signature par le locataire, sur une convention de sortie valant reconnaissance de dettes, un montant de 895 fr. sous la rubrique « loyer dû », créant fallacieusement l'illusion que ledit locataire se reconnaissait être débiteur de ce montant et d'avoir fait suivre ce document au service contentieux de la gérance qui en a demandé l'encaissement à l'entreprise s'étant portée caution.
B.
Le 19 septembre 2013, A._ a formé opposition contre l'ordonnance pénale du 23 mai 2013, l'acte valant au surplus demande de restitution de délai et de nouvelle notification.
Par décision du 26 septembre 2013, le Ministère public de l'arrondissement de Lausanne a constaté que l'ordonnance pénale du 23 mai 2013 avait été valablement notifiée, rejeté la demande de nouvelle notification respectivement de restitution du délai d'opposition et dit que l'ordonnance du 23 mai 2013 était exécutoire.
C.
Statuant sur le recours formé par A._, la Chambre pénale de recours du Tribunal cantonal vaudois l'a rejeté par arrêt du 10 octobre 2013.
D.
A._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt. Il conclut, avec suite de frais et dépens, principalement à sa réforme en ce sens que le délai d'opposition contre l'ordonnance du 23 mai 2013 lui est restitué. Subsidiairement, il conclut à l'annulation de l'arrêt entrepris.
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 les art. 9, 29 Cst. et 6 CEDH, le recourant fait grief à la cour cantonale d'avoir violé son droit d'être entendu en refusant les mesures d'instruction qu'il avait requises.
1.1. Le droit d'être entendu, tel qu'il est garanti par l'art. 29 al. 2 Cst. et l'art. 3 al. 2 let. c CPP, comprend notamment pour le justiciable le droit d'obtenir l'administration des preuves pertinentes et valablement offertes, de participer à l'administration des preuves essentielles et de se déterminer sur son résultat lorsque cela est de nature à influer sur la décision à rendre (<ref-ruling> consid. 3.1 p. 277; <ref-ruling> consid. 2a/aa p. 16; <ref-ruling> consid. 3a p. 51). Toutefois, le magistrat peut renoncer à l'administration de certaines preuves, notamment lorsque les faits dont les parties veulent rapporter l'authenticité ne sont pas importants pour la solution du litige. Ce refus d'instruire ne viole le droit d'être entendu que si l'appréciation anticipée de la pertinence du moyen de preuve offert, à laquelle le juge a ainsi procédé, est entachée d'arbitraire (<ref-ruling> consid. 5.3 p. 236).
1.2. Selon l'<ref-law>, un prononcé est réputé notifié lorsque, expédié par recommandé, il n'a pas été retiré dans les sept jours à compter de la tentative infructueuse de remise du pli, si la personne concernée devait s'attendre à une telle remise. Cette disposition reprend les principes développés par la jurisprudence et qui prévalaient avant l'entrée en vigueur du code de procédure pénale suisse le 1 er janvier 2011 (arrêt 6B_422/2011 du 7 octobre 2011 consid. 1.2; cf. <ref-ruling> consid. 4 p. 51 s.; <ref-ruling> consid. 1.2.3 p. 399).
La personne concernée ne doit s'attendre à la remise d'un prononcé que lorsqu'il y a une procédure en cours qui impose aux parties de se comporter conformément aux règles de la bonne foi, à savoir de faire en sorte, entre autres, que les décisions relatives à la procédure puissent leur être notifiées. Le devoir procédural d'avoir à s'attendre avec une certaine vraisemblance à recevoir la notification d'un acte officiel naît avec l'ouverture d'un procès et vaut pendant toute la durée de la procédure (ATF <ref-ruling> consid. 1.2.3 p. 399).
1.3. Aux termes de l'art. 5 al. 3 Cst., les organes de l'État et les particuliers doivent agir de manière conforme aux règles de la bonne foi. De ce principe général découle notamment le droit fondamental du particulier à la protection de sa bonne foi dans ses relations avec l'État, consacré à l'art. 9 in fine Cst., dont le Tribunal fédéral contrôle librement le respect (<ref-ruling> consid. 8.3.1 p. 53 et les références citées). Le principe de la bonne foi est également concrétisé à l'<ref-law>.
1.4. Le recourant soutient qu'à la fin de son interrogatoire par la police le 29 novembre 2012, il lui aurait été exposé par le policier que l'affaire n'aurait pas de suite. Sur la base de cette information, il serait parti du principe que l'enquête pénale était terminée et il ne pouvait s'attendre à recevoir, six mois plus tard, une ordonnance pénale. Afin d'établir ces éléments, le recourant a requis l'audition du policier ayant mené son interrogatoire ainsi que d'une autre personne présente lors de l'interrogatoire.
La cour cantonale a refusé ces auditions. En substance, elle a retenu qu'il ressortait du procès-verbal d'audition du recourant du 29 novembre 2012 qu'il était entendu comme prévenu, sur ordre du procureur, et que cette audition faisait suite à une première audition lors de laquelle il avait été entendu comme personne appelée à donner des renseignements. Le recourant n'aurait ainsi pas été entendu une seconde fois sur les mêmes faits si le procureur envisageait de classer la procédure. De plus, le rapport de police ne faisait pas état des assurances que le recourant prétendait avoir reçues.
L'appréciation cantonale ne peut être suivie. En effet, les informations figurant dans le procès-verbal et dans le rapport de police ne donnent pas d'indice sur ce qui s'est dit après l'audition du recourant. En outre, le rapport de police vise à relater les faits et n'est pas là pour transcrire l'appréciation juridique de la situation par le policier qui le rédige. Par conséquent, le seul moyen d'établir si le recourant a été ou non informé qu'il n'y aurait pas de suite à l'affaire est l'audition des personnes présentes à ce moment-là. Ce fait est en outre pertinent. En effet, malgré les informations figurant dans le procès-verbal, le recourant, qui n'était pas assisté d'un avocat durant ses auditions, ni durant la procédure, pouvait, de bonne foi, se fier aux affirmations d'un policier, si celles-ci sont avérées. Contrairement à l'affaire ayant donné lieu à l'arrêt sur lequel la cour cantonale se fonde (arrêt 6B_158/2012 du 27 juillet 2012 dans lequel la prévenue avait été interpellée avec 6 g nets d'héroïne, comportement dont elle ne soutenait pas avoir pensé qu'il était licite), l'évidence de l'illicéité du comportement du recourant n'est pas à ce point telle qu'elle s'imposait à lui dans le cas où il aurait effectivement reçu des assurances contraires de la part du policier.
Par conséquent, la cause sera renvoyée à l'autorité cantonale pour qu'elle procède aux auditions des témoins requises par le recourant. S'il s'avère que le recourant a été informé d'une quelconque façon que l'affaire n'aboutirait pas à sa condamnation, il doit être protégé dans sa bonne foi. Dès lors, la fiction de la notification fondée sur l'art. 85 al. 4. let. a CPP ne pourrait pas être appliquée et l'ordonnance du 23 mai 2013 devrait être considérée comme notifiée au moment où le recourant, respectivement son avocat, en a pris connaissance.
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. L'arrêt attaqué doit être annulé et la cause renvoyée à l'autorité précédente pour nouvelle instruction et nouvelle décision.
Le recourant obtient gain de cause. Il ne supporte pas de frais (art. 65 al. 2 et 66 al. 1 LTF). Il peut prétendre à de pleins dépens (<ref-law>).

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 à l'autorité cantonale pour nouvelle instruction et nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires.
3.
Le canton de Vaud versera au recourant une indemnité de 2000 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 Chambre des recours pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 12 mai 2014
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président: Mathys
La Greffière: Livet