Faits : A. Par jugement du 19 juin 2013, le Tribunal criminel de l'arrondissement de Lausanne a notamment constaté que X._ s'était rendu coupable de meurtre, lésions corporelles simples, lésions corporelles simples qualifiées, vol, dommage à la propriété, injure, menaces, violation de domicile, infraction à la Loi fédérale sur les étrangers, infraction à la Loi fédérale sur les armes, les accessoires d'armes et les munitions, et contravention à la Loi fédérale sur les stupéfiants (I). Il l'a condamné à une peine privative de liberté de douze ans, sous déduction de 790 jours de détention avant jugement, à une peine pécuniaire d'un jour-amende à 10 fr. et à une amende de 100 fr. (II). Le tribunal a ordonné que X._ soit soumis à un traitement psychothérapeutique ambulatoire en cours de détention (III) et qu'il soit maintenu en détention à titre de mesure de sûreté (IV). Ce jugement était partiellement complémentaire à celui rendu par la même autorité le 3 mars 2011 (V). En substance, les faits reprochés en lien avec les infractions contre la vie et l'intégrité corporelle sont les suivants. Au cours de la nuit du 21 au 22 avril 2011, X._, alors sous l'effet de l'alcool et de stupéfiants, a cambriolé un atelier en emportant notamment un poignard et un petit couteau. Au cours d'une altercation survenue vers 5h40, le prévenu s'est servi de ces couteaux pour asséner des coups à A._ et son frère B._. Le premier a subi des blessures à l'arrière d'une oreille, dans le cuir chevelu, à l'arrière du crâne et sur le flanc gauche. Le second, souffrant de huit lésions, a succombé à ses blessures le même jour. Mandatés par le Procureur en cours d'enquête, les Docteurs C._ et D._ (Département de psychiatrie du CHUV) ont procédé à l'expertise psychiatrique de X._ et ont établi un rapport en date du 3 novembre 2011. B. Saisie d'un appel du Ministère public, la Cour d'appel pénale du Tribunal cantonal vaudois a, par jugement du 6 novembre 2013, modifié le chiffre III du jugement de première instance et a ordonné que X._ soit soumis à une mesure d'internement au sens de l'art. 64 al. 1 let. a CP. C. Contre ce jugement, X._ forme un recours en matière pénale et conclut, avec suite de frais et dépens, principalement à sa réforme, en ce sens qu'il ne soit pas soumis à une mesure d'internement mais à un traitement psychothérapeutique ambulatoire en cours de détention. Subsidiairement, il conclut à l'annulation du jugement et au renvoi de la cause à l'autorité cantonale pour nouvelle instruction et nouvelle décision dans le sens des considérants. Il sollicite en outre l'assistance judiciaire. Invités à se déterminer sur le recours, le cour cantonale y a renoncé en se référant aux considérants de sa décision, alors que le Ministère public a conclu au rejet du recours.