Faits :
A.
Par jugement du 5 novembre 2019, le Tribunal de police de l'arrondissement de La Côte a reconnu A._ coupable de vol et l'a condamné à une peine pécuniaire de 30 jours-amende à 50 fr. le jour, avec sursis pendant deux ans, et à une amende de 375 francs. Il a en outre condamné A._ au paiement de 458 fr. 60 en faveur de B._.
B.
Statuant sur appel de A._ par jugement du 20 février 2020, la Cour d'appel pénale du Tribunal cantonal vaudois l'a rejeté et a confirmé le jugement de première instance.
La condamnation repose en substance sur les faits suivants.
Le 30 octobre 2018, vers 20h05, dans la station d'essence C._ sise à Nyon, A._ a dérobé le porte-monnaie de marque Gucci appartenant à B._, que ce dernier avait oublié sur le guichet quelques minutes plus tôt. Ce porte-monnaie contenait une carte bancaire, une carte d'identité ainsi qu'un permis de conduire.
B._ a déposé plainte et s'est constitué partie civile le 1er novembre 2018.
C.
A._ forme un recours en matière pénale contre la décision cantonale et conclut, avec suite de frais et dépens, à titre principal, à son acquittement du chef d'inculpation de vol. Subsidiairement, il conclut à la réforme du jugement cantonal en ce sens qu'il est condamné pour vol d'importance mineure. Plus subsidiairement, il conclut au renvoi de la cause à la cour cantonale pour nouvelle décision.

Considérant en droit :
1.
Le recourant fait grief à la cour cantonale d'avoir apprécié les preuves et établi les faits de manière arbitraire. Il se plaint à cet égard d'une violation du principe "in dubio pro reo".
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. La présomption d'innocence, garantie par les <ref-law>, 32 al. 1 Cst., 14 par. 2 Pacte ONU II et 6 par. 2 CEDH, ainsi que son corollaire, le principe " in dubio pro reo ", concernent tant le fardeau de la preuve que l'appréciation des preuves au sens large. En tant que règle sur le fardeau de la preuve, elle signifie, au stade du jugement, que ce fardeau incombe à l'accusation et que le doute doit profiter au prévenu. Comme règle d'appréciation des preuves, la présomption d'innocence signifie que le juge ne doit pas se déclarer convaincu de l'existence d'un fait défavorable à l'accusé si, d'un point de vue objectif, il existe des doutes quant à l'existence de ce fait. Il importe peu qu'il subsiste des doutes seulement abstraits et théoriques, qui sont toujours possibles, une certitude absolue ne pouvant être exigée. Il doit s'agir de doutes sérieux et irréductibles, c'est-à-dire de doutes qui s'imposent à l'esprit en fonction de la situation objective. Lorsque l'appréciation des preuves et la constatation des faits sont critiquées en référence au principe " in dubio pro reo ", celui-ci n'a pas de portée plus large que l'interdiction de l'arbitraire (<ref-ruling> consid. 1.1 p. 155 s. et les références citées).
1.2. Pour imputer au recourant la commission du vol litigieux, la cour cantonale s'est fondée sur les images de vidéosurveillance de la station d'essence qu'elle a jugées probantes. Elle a constaté que le recourant avait pris un objet sur sa droite, sur le devant du comptoir, objet qui était le porte-monnaie de l'intimé, laissé quelques minutes auparavant. Si, dans l'intervalle un autre client était passé, celui-ci n'avait toutefois pris que ses propres achats. Selon la cour cantonale, il ressortait clairement des images, un bref retour du recourant faisant le geste de prendre un objet sur sa droite, après avoir jeté un coup d'oeil à gauche, alors qu'il n'avait rien déposé auparavant, respectivement rien oublié. La cour cantonale a écarté la version du recourant selon laquelle il avait simplement repris son porte-cartes, dès lors qu'il ressortait des images de vidéosurveillance qu'il avait conservé ses deux cartes sur lui, qu'il avait rangées ensuite dans son porte-monnaie.
1.3. Contestant être l'auteur du vol, le recourant fait valoir que les images de vidéosurveillance seraient floues et saccadées. Ainsi, le porte-monnaie n'apparaîtrait à aucun moment sur les images de vidéosurveillance et ces images ne permettraient pas de percevoir le geste qui lui est reproché.
Le visionnement de l'enregistrement vidéo en cause permet de distinguer tant le dépôt et l'oubli d'un objet par l'intimé sur la tablette située sous le guichet, que les gestes du recourant décrits par la cour cantonale (bref retour, regard de côté, saisie d'un objet). Dans ces circonstances, c'est sans arbitraire que la cour cantonale a retenu que le recourant s'était saisi du porte-monnaie de l'intimé.
Pour le surplus, le recourant se livre à une critique essentiellement appellatoire des faits établis, en particulier lorsqu'il affirme que, si le plaignant avait véritablement oublié son porte-monnaie, un tiers aurait dit quelque chose, ou qu'il ne serait pas exclu qu'un autre client eût pu s'en saisir.
Le grief doit être rejeté dans la mesure où il est recevable.
1.4. Le recourant ne saurait déduire d'une phrase d'un des considérants du jugement cantonal, dont il ressort que la présomption d'innocence se confondrait avec l'interdiction générale de l'arbitraire, que la cour cantonale aurait limité son pouvoir d'examen des preuves à l'arbitraire. Traitant les critiques du recourant relatives à l'appréciation des preuves faite par le juge précédent, la cour cantonale a retenu que les images de vidéosurveillance étaient probantes. Elle a, à son tour, décrit les faits qui ressortaient de l'enregistrement (jugement entrepris consid. 3.3 p. 11: "on voit que l'intéressé conserve [...]", "on voit également clairement [...]") en indiquant les minutes pertinentes, et s'est livrée à sa propre appréciation. Le recourant est irrecevable à interpréter le pouvoir d'examen de la cour cantonale en prétendant qu'elle aurait "repris l'argumentation" du tribunal de première instance ou qu'elle aurait "paraphrasé" un considérant. En tout état, rien n'indique que la cour cantonale aurait fait l'économie d'une nouvelle appréciation des preuves.
2.
Le recourant reproche à la cour cantonale de ne pas avoir traité son grief, qu'il aurait plaidé en appel, tendant à admettre l'infraction privilégiée de vol d'importance mineure. Il invoque une violation de son droit d'être entendu en lien avec l'<ref-law>.
2.1.
2.1.1. La jurisprudence a déduit de l'art. 29 al. 2 Cst. l'obligation pour l'autorité de motiver sa décision, afin que l'intéressé puisse se rendre compte de la portée de celle-ci et exercer son droit de recours à bon escient (<ref-ruling> consid. 3.4.3 p. 46; <ref-ruling> consid. 2.1 p. 145). Pour satisfaire à ces exigences, il suffit que l'autorité mentionne, au moins brièvement, les motifs qui l'ont guidée et sur lesquels elle a fondé son raisonnement. Elle n'a toutefois pas l'obligation d'exposer et de discuter tous les faits, moyens de preuve et griefs invoqués par les parties, mais peut au contraire se limiter à l'examen des questions décisives pour l'issue du litige (<ref-ruling> consid. 4.2 p. 157; <ref-ruling> consid. 3.2.1 p. 565). La motivation peut d'ailleurs être implicite et résulter des différents considérants de la décision (ATF <ref-ruling> consid. 3.2.1 p. 565).
2.1.2. L'<ref-law> prévoit que si l'acte ne visait qu'un élément patrimonial de faible valeur ou un dommage de moindre importance, l'auteur sera, sur plainte, puni d'une amende. Un élément patrimonial est de faible valeur au sens de cette disposition, s'il ne vaut pas plus que 300 francs (<ref-ruling> consid. 3.1 p. 133; <ref-ruling> consid. 1a p. 156; <ref-ruling> consid. 3d p. 119).
Selon la jurisprudence, c'est l'intention qui est déterminante et non le résultat obtenu. L'<ref-law> n'est applicable que si l'auteur n'avait d'emblée en vue qu'un élément patrimonial de faible valeur (ATF <ref-ruling> consid. 1a p. 156; <ref-ruling> consid. 2a p. 160; arrêt 6B_158/2018 du 14 juin 2018 consid. 2.2).
De jurisprudence constante, lorsque l'auteur s'empare d'un porte-monnaie, un produit de l'infraction de plus de 300 fr. peut entrer en considération. Sans indices contraires concrets, le dol éventuel correspondant doit être retenu (<ref-ruling> consid. 2c p. 201; cf. arrêts 6B_158/2018 du 14 juin 2018 consid. 2; 6B_208/2010 du 15 juillet 2010 consid. 3).
2.2. Contrairement à ce que prétend le recourant, la cour cantonale a retenu que la qualification de l'infraction de vol n'était pas "en elle-même" contestée.
En tout état, il est établi et non contesté que le vol visait un porte-monnaie de marque Gucci, lequel valait 370 fr. indépendamment de son contenu (cf. jugement entrepris consid. 2 p. 8; jugement de première instance consid. 4 p. 10). Cela étant, la motivation du jugement entrepris permet de comprendre que les juges cantonaux ont implicitement exclu l'application de l'<ref-law>. Au vu de la jurisprudence publiée et constante du Tribunal fédéral (cf. consid. 2.1.2) et en l'absence d'indice contraire de la volonté du recourant, la cour cantonale pouvait exclure d'emblée et de manière implicite que l'acte visait un élément patrimonial de faible valeur et écarter ainsi l'application de l'<ref-law>. Ce d'autant qu'il visait un porte-monnaie Gucci qui, du propre aveu du recourant, "ne pass[e] normalement pas inaperçu" (mémoire de recours ch. 32 p. 9).
Le grief du recourant doit être rejeté dans la mesure où il est recevable.
3.
Le recours doit être rejeté dans la mesure où il est recevable. Le recourant, qui succombe, supporte les frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté dans la mesure où il est recevable.
2.
Les frais judiciaires, arrêtés à 3'000 fr., sont mis à la charge du recourant.
3.
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 3 novembre 2020
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Klinke