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 (<ref-law>) 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é.

Considérant en droit :
1.
Le recourant reproche à la Chambre pénale de recours de ne pas l'avoir interpellé sur le prétendu non-paiement de l'avance de frais avant de rendre sa décision. Il y voit une violation de son droit d'être entendu ainsi que la violation du droit fédéral dans l'application des art. 91 al. 5 et 382 al. 2 CPP. Il se réfère au récépissé postal daté du 30 juin 2016 produit devant le Tribunal fédéral comme preuve attestant du paiement dans le délai imparti.
2.
Les faits et moyens de preuve nouveaux sont prohibés devant le Tribunal fédéral (<ref-law>); il n'y a exception à cette règle que lorsque c'est la décision de l'autorité précédente qui, pour la première fois, a rendu pertinents ces faits ou moyens de preuve, ce qu'il appartient au recourant de démontrer (<ref-ruling> consid. 3 p. 395).
Tel est le cas en l'espèce s'agissant de la pièce produite par le recourant susceptible d'établir qu'il a versé les sûretés requises en temps utile.
3.
3.1. Selon l'<ref-law>, la direction de la procédure de l'autorité de recours peut astreindre la partie plaignante à fournir des sûretés dans un délai déterminé pour couvrir les frais et indemnités éventuels. L'art. 136 est réservé (al. 1). Si les sûretés ne sont pas fournies dans le délai imparti, l'autorité de recours n'entre pas en matière sur le recours (al. 2). A teneur de l'<ref-law>, un paiement à l'autorité pénale est effectué dans le délai prescrit lorsque le montant est versé en faveur de l'autorité pénale à la Poste suisse ou débité d'un compte bancaire ou postal en Suisse le dernier jour du délai au plus tard. Il appartient à la partie plaignante d'établir la preuve que le paiement a été effectué en temps utile. En cas de paiement tardif, l'autorité doit inviter la partie concernée à fournir la preuve qu'elle a acquitté à temps le montant requis (arrêt 6B_310/2016 du 19 janvier 2017 consid. 2.7 destiné à la publication).
3.2. Interpellée sur le récépissé d'un paiement de 800 fr. effectué par la Fondation des parkings, employeur du recourant, le 30 juin 2016 sur le compte bancaire du pouvoir judiciaire, l'autorité précédente a répondu qu'aucun avis de crédit ne lui était parvenu avec la référence à la procédure concernée comme le recourant était invité à le faire par l'ordonnance du 23 juin 2016. Par suite de recherches effectuées auprès du Service financier du pouvoir judiciaire, il était apparu qu'un versement de 800 fr. avait été effectué par la Fondation des parkings dans une autre cause, montant crédité le 4 juillet 2016, alors que le versement des sûretés pour cette autre procédure, également de 800 fr., avait déjà été opéré le 31 mai 2016. Le montant de 800 fr., ainsi crédité à tort, avait été restitué à la suite de l'arrêt rendu dans cette autre cause le 28 septembre 2016. L'autorité précédente considère ainsi que l'erreur dans la désignation des références de la cause est seule imputable au recourant dont le recours doit être rejeté.
3.3. Il ressort de la détermination de la cour cantonale que celle-ci ne conteste pas avoir reçu en temps utile le montant des sûretés requises. Que, par la négligence de l'employeur du recourant, la somme ait été affectée à une autre cause est sans portée quant au fait que ce dernier a prouvé que l'argent est bien arrivé sur le compte bancaire du destinataire, à savoir la caisse du pouvoir judiciaire. Le recourant qui s'était acquitté des sûretés était recevable à recourir. Cela rend superflu l'examen des griefs du recourant quant à la violation du droit d'être entendu, étant précisé que la jurisprudence rendue à ce jour enjoint l'autorité de recours à interpeller la partie sur la preuve qu'elle a acquitté à temps le montant requis en cas de paiement tardif (consid. 3.1).
4.
Le recours doit être admis et la cause renvoyée à la juridiction précédente pour reprise de la procédure et fixation d'un nouveau délai de paiement. Il est statué sans frais (art. 66 al. 1 et 4 LTF). La négligence du recourant dans la désignation inexacte du numéro de procédure ne saurait toutefois être imputée à l'Etat de Genève, en sorte qu'il ne saurait prétendre à des dépens.

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué est annulé et la cause est renvoyée à l'autorité cantonale pour nouvelle décision.
2.
Il n'est pas perçu de frais judiciaires, ni alloué de dépens.
3.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 6 mars 2017
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Président : Denys
La Greffière : Musy