Faits : A. Le 4 octobre 2014, une manifestation non autorisée dont le but était de protester contre le défilé du bicentenaire de la police a eu lieu à Genève. Environ 250 personnes, dont des membres du Black Block, y ont participé. Cette manifestation a dégénéré et des actes de violence sur des biens et des personnes ont été commis. X._ était en tête du cortège, vêtu notamment d'un pull à capuche noir et d'une casquette et filmait l'évènement au moyen d'une caméra. A la suite de diverses plaintes, une instruction pénale a été ouverte à l'encontre de X._ pour violence et menace contre les fonctionnaires (art. 285 CP) et émeute (art. 260 CP). Il lui était notamment reproché d'avoir pris part à ladite manifestation ainsi que d'avoir insulté, lors de celle-ci, un agent de police. B. Par ordonnance du 25 septembre 2015, le Ministère public genevois a partiellement classé la procédure dirigée contre X._ du chef d'émeute, faute d'avoir pu établir avec certitude qu'il avait fait partie des manifestants ayant commis les dégâts du 4 octobre 2014. Les frais de procédure de 500 fr. étaient mis à sa charge et l'indemnité pour les frais de défense requise a été refusée. Par ordonnance pénale du même jour, le Ministère public a notamment déclaré X._ coupable de violence ou menaces contre les autorités et les fonctionnaires (art. 285 CP) et d'injures (art. 177 al. 1 CP). C. Par arrêt du 18 décembre 2015, la Cour de justice de la République et canton de Genève, Chambre pénale de recours, a rejeté le recours formé par X._ contre l'ordonnance de classement partiel qu'elle a confirmée et l'a condamné aux frais de la procédure. D. Le recourant forme un recours en matière pénale contre l'arrêt cantonal et conclut, avec suite de frais et dépens, à ce que l'ensemble des frais de procédure cantonale soit mis à la charge du canton de Genève et à ce qu'une indemnité équitable de 7'158 fr. 30 lui soit allouée en application de l'art. 429 al. 1 let. a CPP. La cour cantonale a renoncé à se déterminer sur le mémoire de recours en se référant aux considérants de son arrêt. Le Ministère public a fait part de ses observations et a conclu au rejet du recours. Le recourant s'est prononcé sur les déterminations du Ministère public.