Faits : A. X._ travaille en qualité d'agent du stationnement au sein de la Fondation des parkings. Le 17 décembre 2015, il a déposé une plainte pénale à la suite d'une agression subie durant son service. Le 3 juin 2016, le Ministère public de la République et canton de Genève a prononcé une ordonnance pénale pour une partie des infractions dénoncées et de non-entrée en matière partielle pour les autres infractions. B. X._ a interjeté un recours contre l'ordonnance de non-entrée en matière auprès de la Chambre pénale des recours de la Cour de justice du canton de Genève. Par ordonnance du 23 juin 2016, la Chambre pénale a imparti au recourant un délai au 7 juillet 2016 pour fournir des sûretés à hauteur de 800 francs. C. Par arrêt du 21 juillet 2016, la Chambre pénale a constaté que X._ n'avait pas versé dans le délai imparti les sûretés de 800 fr. requises par l'ordonnance du 23 juin 2016. Elle a considéré que le non-versement des sûretés imposait à lui seul de ne pas entrer en matière sur le recours (art. 383 al. 2 CPP) et a rayé la cause du rôle. D. X._ forme un recours en matière pénale auprès du Tribunal fédéral contre cet arrêt. Il conclut à son annulation et au renvoi de la décision à l'autorité cantonale pour qu'il soit entré en matière sur son recours. Il produit devant le Tribunal fédéral un récépissé postal daté du 30 juin 2016 attestant d'un versement de 800 fr. sur le compte bancaire du pouvoir judiciaire émanant de la Fondation des parkings, son employeur. E. Interpellée, l'autorité cantonale s'est déterminée et a conclu au rejet du recours. Son écriture a été transmise au recourant qui a persisté dans ses conclusions. Le Ministère public ne s'est pas prononcé.