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. 