Faits : A. Par jugement du 23 octobre 2015, le Tribunal correctionnel de l'arrondissement de La Côte a reconnu X._ coupable d'infraction grave et d'infraction à la LStup (art. 19 al. 1 let. b, c et d et 19 al. 2 let. a LStup); il a été condamné à une peine privative de liberté de treize mois, avec sursis pendant trois ans, ainsi qu'au paiement d'une amende de 700 fr., une peine privative de liberté de substitution de sept jours étant prévue au cas où l'amende ne serait pas payée. Par l'intermédiaire de son avocat, X._ a déposé une annonce d'appel à l'encontre de ce jugement le 28 octobre 2015. Le lendemain, soit le 29 octobre 2015, le Tribunal correctionnel de l'arrondissement de La Côte a notifié une copie complète du jugement à X._ et lui a imparti un délai de vingt jours pour déposer une déclaration d'appel. Le 20 novembre 2015, X._ a adressé, par l'entremise de son avocat, une requête de restitution de délai pour déposer une déclaration d'appel auprès de la Cour d'appel pénale du Tribunal cantonal (art. 94 CPP). Une déclaration d'appel datée du 19 novembre 2015 accompagnait cette requête. Par avis du 24 novembre 2015, le Président de la Cour d'appel pénale a informé X._ que sa requête de restitution de délai était rejetée, aucun motif d'empêchement n'ayant été rendu vraisemblable, qu'il apparaissait en outre que la déclaration d'appel pourrait être considérée comme irrecevable et qu'en application de l'art. 403 al. 2 CPP, un délai au 4 décembre 2015 lui était imparti pour se prononcer sur la recevabilité de l'appel. X._ a présenté des déterminations le 17 décembre 2015, dernier jour du délai prolongé à sa demande, qu'il a complétées par courrier du 22 décembre 2015. B. Le 23 décembre 2015, la Cour d'appel pénale du Tribunal cantonal vaudois a déclaré l'appel interjeté par X._ irrecevable. Elle a considéré en substance que la déclaration d'appel était tardive, car déposée à la Poste le lendemain de l'expiration du délai. En expliquant ce retard au motif d'une confusion intervenue le 19 novembre 2015 au sein du secrétariat de son défenseur d'office concernant la personne qui devait acheminer le courrier de l'étude à la Poste, X._ ne rendait pas vraisemblable un motif d'empêchement valable. Il n'y avait par conséquent pas lieu de restituer le délai au sens de l'art. 94 CPP, de sorte que la déclaration d'appel, déposée hors délai, était irrecevable. C. X._ forme un recours en matière pénale au Tribunal fédéral contre ce jugement, concluant à la restitution du délai pour déposer sa déclaration d'appel contre le jugement du Tribunal correctionnel de l'arrondissement de La Côte du 23 octobre 2015, à ce qu'il lui soit donné acte du dépôt, le 20 novembre 2015, d'une déclaration d'appel, à ce qu'il soit ordonné la notification d'une copie de cette déclaration d'appel au Ministère public de l'arrondissement de La Côte en l'informant qu'il a la faculté, dans un délai de vingt jours dès la notification de la présente ordonnance, de présenter par écrit au greffe de la Cour d'appel pénale une demande de non-entrée en matière motivée ou une déclaration d'appel joint, conformément à l'art. 401 CPP, et à ce que les parties soient informées des voie et délai de recours. D. Invités à se déterminer sur le mémoire de recours, la cour cantonale et le Ministère public y ont renoncé, se référant aux considérants de la décision entreprise.