Faits :
A.
Par jugement du 28 mai 2019, le Tribunal correctionnel de l'arrondissement de Lausanne a reconnu A._ coupable d'infraction grave à la loi sur les stupéfiants (I), a révoqué le sursis partiel octroyé le 5 juillet 2017 par le Tribunal d'arrondissement de Lausanne (II), l'a condamné à une peine privative de liberté d'ensemble de 39 mois, sous déduction de la détention subie avant jugement (III) et a prononcé son expulsion du territoire suisse pour une durée de 20 ans (VII).
B.
Statuant par jugement du 5 novembre 2019 sur appel de A._ et appel joint du ministère public, la Cour d'appel pénale du Tribunal cantonal vaudois a supprimé le ch. II du jugement de première instance et a condamné A._ à une peine privative de liberté d'ensemble de 45 mois, sous déduction de la détention subie avant jugement (III). Pour le surplus, elle a confirmé le jugement de première instance.
En substance, les faits retenus par la cour cantonale sont les suivants.
Né en 1996, A._ est ressortissant de Gambie. Il est marié avec une compatriote avec qui il faisait ménage commun en Italie (dans les environs de Rome) avant de se rendre en Suisse. Il a une fille, née en 2019, qui vivrait désormais avec sa compagne en France. Il aurait travaillé tantôt dans une ferme, tantôt dans la restauration. Le revenu mensuel moyen du couple était d'environ 900 euros.
Le 15 octobre 2018, à 22h00, alors qu'il sortait d'un squat, connu comme un repaire notoire de trafiquants de drogue à Lausanne, A._ a été contrôlé par la police en possession de 15 " fingers " de cocaïne d'un poids brut de 165 grammes (équivalant à 63,7 grammes de stupéfiants purs), 50 euros et 486 fr. en espèces, ainsi que deux téléphones cellulaires.
L'extrait du casier judiciaire de A._ fait mention de quatre condamnations prononcées entre le 7 février 2015 et le 5 juillet 2017, à une peine pécuniaire de 30 jours-amende avec sursis pour délit contre la LStup (7 février 2015), à 30 jours de peine privative de liberté pour séjour illégal (26 novembre 2015), à 40 jours-amende et à une amende pour séjour illégal (25 février 2016). Le 5 juillet 2017, A._ a été condamné à 30 mois de peine privative de liberté, dont 15 avec sursis, ainsi qu'à une expulsion du territoire suisse pour une durée de 8 ans, notamment pour séjour illégal, activité lucrative sans autorisation, délit et crime contre la LStup (avec mise en danger de nombreuses personnes).
C.
A._ forme un recours en matière pénale auprès du Tribunal fédéral contre la décision cantonale et conclut, avec suite de frais et dépens, principalement, à sa libération de l'infraction de crime contre la LStup, au constat qu'il a subi 252 jours de détention injustifiée (dont 244 dans des conditions illicites), à la condamnation de l'Etat de Vaud au paiement des sommes de 77'000 fr. et 10'900 fr. en réparation du tort moral subi, à sa libération immédiate, à la restitution des montants confisqués et à la destruction de la drogue séquestrée. Subsidiairement, il conclut à l'annulation de la décision et au renvoi de la cause à la cour cantonale pour nouvelle décision dans le sens des considérants. Il sollicite en outre le bénéfice de l'assistance judiciaire.

Considérant en droit :
1.
Selon le recourant, les faits sur lesquels repose sa condamnation ont été établis de manière arbitraire.
1.1. Le Tribunal fédéral n'est pas une autorité d'appel, auprès de laquelle les faits pourraient être rediscutés librement. Il est lié par les constatations de fait de la décision entreprise (<ref-law>), à moins qu'elles n'aient été établies en violation du droit ou de manière manifestement inexacte au sens des art. 97 al. 1 et 105 al. 2 LTF, soit pour l'essentiel de façon arbitraire au sens de l'art. 9 Cst. Une décision n'est pas arbitraire du seul fait qu'elle apparaît discutable ou même critiquable; il faut qu'elle soit manifestement insoutenable et cela non seulement dans sa motivation mais aussi dans son résultat. Le Tribunal fédéral n'entre pas en matière sur les critiques de nature appellatoire (<ref-ruling> consid. 1.1 p. 155 s. et les références citées).
1.2. La cour cantonale a considéré que les sommes d'argent retrouvées sur le recourant n'étaient pas compatibles avec le modique revenu mensuel de son couple. Les raisons pour lesquelles le recourant prétendait être venu en Suisse, à savoir qu'il était venu de Rome à Lausanne afin de chercher des habits dont il peinait à estimer la valeur et dont il ne savait où ils se situaient, n'étaient pas plausibles ni vérifiées par les éléments du dossier. L'assertion selon laquelle le recourant avait l'intention de repartir sitôt les habits récupérés était infirmée par le fait qu'il était en possession d'un billet de train dépourvu de retour. Les déclarations selon lesquelles il était resté environ une heure dans le squat avant son arrestation n'étaient pas crédibles et étaient contredites par les constatations de la police qui l'avait vu entrer dans le bâtiment pour en ressortir quelques minutes plus tard.
La cour cantonale a qualifié d'invraisemblable la version selon laquelle le recourant avait pris par mégarde, en sortant du squat, une veste contenant de la drogue qui ne lui appartenait pas. Les " fingers " retrouvés sur le recourant le 15 octobre 2018 portaient le même code qui était apposé sur la drogue qu'il détenait lors de sa précédente arrestation le 8 novembre 2016 et pour laquelle il avait admis s'être livré à un trafic de cocaïne. Il était invraisemblable que le recourant eût enfilé par mégarde une veste contenant de la cocaïne avec ce code d'identification et que le propriétaire d'une veste contenant de la drogue pour une valeur vénale de 15'000 fr. eût laissé ce vêtement à l'abandon, sans surveillance, dans un lieu ouvert à tous.
La cour cantonale en a conclu que le recourant avait rejoint la même filière que celle à laquelle il appartenait lors de son précédent séjour en Suisse pour recommencer à se livrer au trafic de cocaïne.
Elle a retenu qu'il s'était rendu coupable d'infractions à l'art. 19 al. 1 let. b et d et 19 al. 2 let. a LStup.
1.3. Le recourant affirme que les explications qu'il a apportées quant aux motifs de sa venue en Suisse, à la drogue retrouvée dans la veste et le temps passé dans le squat, sont crédibles et ne sont pas mises en doute valablement par les éléments du dossier. Un tel procédé est purement appellatoire, partant irrecevable (cf. <ref-law>). Dans la mesure où la cour cantonale a démontré de façon motivée en quoi la version du recourant n'était pas plausible, voire invraisemblable, il importe peu de savoir si le recourant est resté une heure ou quelques minutes dans le squat. Contrairement à ce que prétend le recourant, la cour cantonale a écarté la version selon laquelle il avait l'intention de rentrer, non pas sur la seule base du billet de train mais en se fondant sur plusieurs éléments plaidant en faveur d'un séjour en Suisse dédié au trafic de cocaïne. Par ailleurs, le recourant échoue à démontrer l'arbitraire du constat de la similitude des codes estampillant la drogue saisie lors de ses deux arrestations, au seul motif que l'un d'eux comporterait le numéro " un " en chiffre arabe (A1) et l'autre en chiffre romain (AI). Les griefs d'arbitraire doivent être rejetés dans la mesure de leur recevabilité.
En définitive, en se fondant sur une constatation exempte d'arbitraire, la cour cantonale pouvait, sans violer le droit fédéral, retenir que le recourant s'est rendu coupable de violation qualifiée de la LStup.
2.
Le recourant reproche à la cour cantonale d'avoir augmenté la peine de 6 mois par rapport à la décision de première instance, sans qu'il ne soit possible d'en saisir les motifs. Il invoque une violation des <ref-law> et 29 al. 2 Cst. et prétend que la peine d'ensemble au sens de l'<ref-law> n'est pas motivée.
2.1.
2.1.1. L'<ref-law> prévoit que le juge fixe la peine d'après la culpabilité de l'auteur. Il prend en considération les antécédents et la situation personnelle de ce dernier ainsi que l'effet de la peine sur son avenir (al. 1). La culpabilité est déterminée par la gravité de la lésion ou de la mise en danger du bien juridique concerné, par le caractère répréhensible de l'acte, par les motivations et les buts de l'auteur et par la mesure dans laquelle celui-ci aurait pu éviter la mise en danger ou la lésion, compte tenu de sa situation personnelle et des circonstances extérieures (al. 2). Le juge dispose d'un large pouvoir d'appréciation dans le cadre de la fixation de la peine.
Le Tribunal fédéral n'intervient que lorsque l'autorité cantonale a fixé une peine en dehors du cadre légal, si elle s'est fondée sur des critères étrangers à l'<ref-law>, si des éléments d'appréciation importants n'ont pas été pris en compte ou, enfin, si la peine prononcée est exagérément sévère ou clémente au point de constituer un abus du pouvoir d'appréciation (<ref-ruling> consid. 1.2 p. 319; <ref-ruling> consid. 5.6 p. 61). L'exercice de ce contrôle suppose que le juge exprime, dans sa décision, les éléments essentiels relatifs à l'acte ou à l'auteur dont il tient compte, de manière à ce que l'on puisse constater que tous les aspects pertinents ont été pris en considération et comment ils ont été appréciés, que ce soit dans un sens aggravant ou atténuant (<ref-law>). Le juge peut passer sous silence les éléments qui, sans abus du pouvoir d'appréciation, lui apparaissent non pertinents ou d'une importance mineure. La motivation doit justifier la peine prononcée, en permettant de suivre le raisonnement adopté. Un recours ne saurait toutefois être admis simplement pour améliorer ou compléter un considérant lorsque la décision rendue apparaît conforme au droit (arrêts 6B_1228/2019 du 10 décembre 2019 consid. 4.1; 6B_1235/2019 du 14 novembre 2019 consid. 2.1; cf. <ref-ruling> consid. 1.2 p. 319; <ref-ruling> consid. 5.6 p. 61).
2.1.2. Selon l'<ref-law>, si, durant le délai d'épreuve, le condamné commet un crime ou un délit et qu'il y a dès lors lieu de prévoir qu'il commettra de nouvelles infractions, le juge révoque le sursis ou le sursis partiel. Si la peine révoquée (widerrufene Strafe; pena di cui è revocata la sospensione condizionale)et la nouvelle peine sont du même genre, il fixe une peine d'ensemble en appliquant par analogie l'<ref-law>. Par " peine révoquée ", il faut entendre la peine dont le sursis est révoqué, ainsi que cela ressort du texte italien.
Aux termes de l'<ref-law>, si, en raison d'un ou de plusieurs actes, l'auteur remplit les conditions de plusieurs peines de même genre, le juge le condamne à la peine de l'infraction la plus grave et l'augmente dans une juste proportion. Il ne peut toutefois excéder de plus de la moitié le maximum de la peine prévue pour cette infraction. Il est en outre lié par le maximum légal de chaque genre de peine.
En cas de révocation du sursis, le juge doit fixer une peine d'ensemble en partant méthodiquement de la peine infligée pour l'infraction nouvellement commise pendant le délai d'épreuve, selon les principes fixés à l'<ref-law>, en tant que " peine de départ " ( Einsatzstrafe). Cette nouvelle peine doit être augmentée en raison de la peine dont le sursis est révoqué, par application analogique du principe de l'aggravation (<ref-ruling> consid. 2.4 p. 152 s.).
2.2. La cour cantonale a retenu que l'infraction la plus grave en cause était celle à l'<ref-law>, passible à elle seule d'une peine privative de liberté d'un an au moins. En se référant aux circonstances retenues par les premiers juges, elle a retenu en substance que le recourant avait opéré avec des quantités de drogue importantes, qu'il avait des antécédents lourds, qu'il niait l'évidence et était mû par pur appât du gain. Il était ainsi ancré dans la délinquance et était insensible à la répression pénale, ce qui constituait un facteur à charge significatif. A décharge, seul le jeune âge du recourant a été pris en compte. Contrairement aux premiers juges, la cour cantonale n'a pas retenu la situation précaire du recourant comme étant une circonstance à décharge, dès lors que, de son propre aveu, les revenus suffisaient à l'entretien du couple.
La cour cantonale a posé un pronostic défavorable s'agissant du sursis partiel accordé le 5 juillet 2017, portant sur 15 mois. Elle a relevé que le recourant avait lourdement trahi la confiance placée en lui, qu'il avait récidivé dans le même type d'infractions durant le délai d'épreuve et peu après sa remise en liberté, qu'il niait l'évidence et avait agi par pur appât du gain, qu'il était revenu en Suisse en faisant fi de l'expulsion prononcée (qui plus est en y envisageant un séjour de longue durée), et qu'il avait renoué avec la criminalité alors que sa compagne était enceinte et que tous deux arrivaient à obtenir des revenus leur permettant de subvenir à leur entretien.
Sur la base de ce qui précède, la cour cantonale a prononcé une peine privative de liberté d'ensemble de 45 mois.
2.3.
2.3.1. Contrairement à ce que prétend le recourant, la cour cantonale ne s'est pas limitée à faire siennes les circonstances retenues par le tribunal correctionnel mais a expressément tenu compte d'éléments à charge en qualifiant leur importance dans la fixation de la peine, ainsi qu'une circonstance à décharge. Elle a exposé pour quel motif elle ne retenait pas la situation économique du recourant à décharge, contrairement aux premiers juges.
Aussi, sur ce point, le grief déduit d'une violation de l'<ref-law> doit être rejeté.
2.3.2. Toutefois, il y a lieu de suivre le recourant en tant qu'il relève que la cour cantonale a prononcé une peine d'ensemble, sans préciser quelle est la peine sanctionnant l'infraction nouvellement commise (" peine de départ ") et dans quelle mesure celle-ci est augmentée en raison de la peine dont le sursis est révoqué. Une telle omission ne permet pas de contrôler la bonne application du droit fédéral (cf. art. 46 al. 1, 2ème phrase et 49 CP) et constitue une violation de l'art. 29 al. 2 Cst. Aussi, il y a lieu d'admettre le recours sur ce point et de renvoyer la cause à la cour cantonale pour qu'elle fixe une peine d'ensemble en application de la méthodologie exposée supra (cf. consid. 2.1.2).
C'est le lieu de préciser qu'à teneur de l'art. 366 al. 2 let. d CP, les faits qui entraînent une modification des inscriptions portées au casier sont inscrits au casier judiciaire. Or, les décisions de révocation du sursis, les conséquences d'une révocation et le prononcé d'une peine d'ensemble impliquent une inscription au casier (cf. art. 5 let. a de l'ordonnance du 29 septembre 2006 sur le casier judiciaire; RS 331). Aussi, pour la bonne tenue du casier judiciaire, il y a lieu de maintenir, dans le dispositif du jugement, la mention de la révocation du sursis.
2.3.3. Pour le surplus, le recourant ne conteste d'aucune manière la révocation du sursis dans son principe, le prononcé d'une peine ferme et son expulsion du territoire suisse. Il ne formule aucun grief relatif à la constatation des conditions de détention et à la réparation du tort moral qui en résulte. Il ne critique pas davantage la confiscation des montants séquestrés. Cela étant, il n'y a pas lieu d'examiner ces points plus avant (<ref-law>).
3.
En conséquence, le recours doit être partiellement admis (cf. consid. 2.3.2), le jugement attaqué annulé s'agissant de la peine et la cause renvoyée à la cour cantonale pour nouvelle décision. Pour le surplus, le recours doit être rejeté dans la mesure où il est recevable. Le recourant a requis l'assistance judiciaire. Il ne supportera pas de frais et peut prétendre à une indemnité de dépens réduite relative à l'admission partielle de son recours (<ref-law>), ce qui rend sa demande d'assistance judiciaire sans objet dans cette mesure. Le recours était, pour le surplus, dénué de chance de succès, si bien que l'assistance judiciaire doit être refusée (art. 64 al. 1 et 2 LTF). Le recourant supportera des frais réduits en raison de l'issue de la procédure et de sa situation financière (art. 65 al. 2 et 66 al. 1 LTF).
Au regard de la nature procédurale du vice examiné (cf. consid. 2.3.2), il peut être procédé au renvoi sans ordonner préalablement un échange d'écritures (cf. <ref-ruling> consid. 3.4.2 p. 296; cf. arrêt 6B_508/2018 du 17 décembre 2018 consid. 3).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis, le jugement attaqué est annulé et la cause est renvoyée à la cour cantonale pour nouvelle décision. Pour le surplus, le recours est rejeté dans la mesure où il est recevable.
2.
La demande d'assistance judiciaire est rejetée dans la mesure où elle n'est pas sans objet.
3.
Une partie des frais judiciaires, arrêtée à 800 fr., est mise à la charge du recourant.
4.
Le canton de Vaud versera en mains du conseil du recourant une indemnité de 1'000 fr. à titre de dépens réduits pour la procédure devant le Tribunal fédéral.
5.
Le présent arrêt est communiqué aux parties et à la Cour d'appel pénale du Tribunal cantonal du canton de Vaud.
Lausanne, le 14 février 2020
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke