Faits : A. Le 19 décembre 2017, X._ a déposé plainte pénale pour escroquerie et faux dans les titres contre les " organes ou employés " de A._ SA, société sise à B._ et dirigée par un nommé C._, ainsi que contre toute personne dont l'enquête permettrait d'établir l'implication dans les faits dénoncés. Ressortissant ukrainien domicilié en Ukraine, X._ a exposé avoir, en été 2016, rencontré, à Moscou, D._, lequel s'est prétendu propriétaire d'un lot de 143 émeraudes brutes d'une valeur totale de 44'455'334,95 USD, entreposé dans les locaux de B._ de la maison A._ SA. A cette occasion, D._ a remis à X._ la copie d'un certificat libellé par A._ SA en date du 6 mai 2016 et signé par C._, attestant qu'il était le bénéficiaire du dépôt portant sur les pierres en question. A ce certificat étaient joints la liste de gemmes et 64 rapports d'identification émis par les cabinets d'expertise E._ (en 2002) et F._ (en 1999-2000), sis respectivement au Royaume-Uni et en Russie. X._ a émis l'intention d'acquérir ce lot de gemmes. Il a remis une copie de son passeport à son interlocuteur, afin que celui-ci fasse établir un certificat de dépôt à son nom par la dépositaire. Les deux intéressés ont eu plusieurs rendez-vous en ville de Moscou. Le 5 août 2016, X._, accompagné d'un interprète, s'est rendu avec un certain G._, représentant de D._, dans les locaux de A._ SA à B._. Sur place, une employée de cette société leur a apporté les émeraudes pour examen, en l'absence de C._. Chaque gemme était numérotée, avec mention séparée de son poids (en carats) et de sa valeur estimée par carat. X._ a été surpris tant par la couleur de certaines pierres que par le fait que celles-ci étaient stockées dans " des sachets plastique et sans le moindre soin ". A l'issue de cet examen, X._ s'est vu remettre, contre signature d'un reçu, un certificat de dépôt, émis à son nom par A._ SA et daté du 3 août 2016. Sous réserve de mentions spécifiques, ce titre était identique à celui précédemment délivré au nom de D._ sous la signature de C._ (valeur de la marchandise, type de gemmes, quantité d'émeraudes, carats). Le titre remis à X._ comporte la mention suivante: " The undersigned, A._ SA (...), a Corporation registered under Swiss law, acting under strict laws in Switzerland, hereby confirms and acknowledges that we are holders in safekeeping and have on deposit, the aforementionned securities/ assets of described Gem stones, being held for the benefit of the beneficiary described herein, together with the Gem Stone's respective documentation. (...) B._ 3rd August 2016". Alors qu'il voulait faire examiner à nouveau les pierres par un expert mandaté par lui, X._ s'est vu répondre par une employée de A._ SA, le 27 septembre 2016, que le certificat de dépôt émis à son nom avait été révoqué par D._. Les mois suivants, c'est en vain que X._ a réclamé les émeraudes auprès de A._ SA. Sur requête de preuve à futur, le Juge de paix du district de Lausanne a ordonné une expertise des pierres litigieuses par décision du 5 juillet 2017. La valeur totale des 143 pierres a été évaluée à 689'957,17 USD, selon le rapport d'expertise établi hors procès le 26 février 2018 et produit par X._. X._ a exposé avoir acquis les émeraudes, le 9 août 2016, contre la cession d'une créance consolidée de 89'740'000 Hryvnia, devise ukrainienne, correspondant à environ 2'900'000 fr. au taux de change du 1er février 2018. B. Par ordonnance du 1er février 2018, le ministère public central du canton de Vaud a refusé d'entrer en matière sur la plainte pénale déposée par X._. S'agissant de l'infraction d'escroquerie, le procureur a considéré que les conditions à l'ouverture d'une procédure pénale n'étaient manifestement pas réunies, faute de compétence des autorités de poursuite pénale suisses (commission de l'infraction à l'étranger). Au demeurant, il a estimé que les éléments constitutifs de l'infraction d'escroquerie n'étaient pas réalisés, considérant, par surabondance que le dommage allégué n'était pas établi. S'agissant de l'infraction de faux dans les titres, le ministère public a mis en doute que les documents incriminés fussent assimilables à des titres. En tout état, ils n'émanaient pas des organes de la société dénoncée. Enfin, le certificat de dépôt du 3 août 2016 ne revêtait pas une valeur probante accrue, de sorte qu'il ne pouvait être considéré comme un faux intellectuel. C. Par arrêt du 16 mai 2018, la Chambre des recours pénale du Tribunal cantonal vaudois a rejeté le recours formé par X._ contre l'ordonnance de non-entrée en matière. D. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre l'arrêt cantonal et requiert, avec suite de frais et dépens, le renvoi de la cause au ministère public pour qu'il ouvre une instruction pour faux dans les titres et escroquerie contre les organes ou employés de A._ SA. E. Invités à se déterminer, la cour cantonale a indiqué se référer à son arrêt du 16 mai 2018, tandis que le ministère public a déposé un mémoire de réponse et a conclu au rejet du recours. Ces déterminations ont été communiquées au recourant qui a répliqué.