Faits : A. Le 20 mars 2013, la Cour des Comptes a adressé au Ministère public une dénonciation de suspicion d'une infraction à l'art. 312 CP fondée sur les informations rassemblées dans le cadre de la mission d'audit qu'elle menait en Ville de A._. Il résultait notamment de cette dénonciation que X._, chef du secteur Voirie du Service travaux et espaces verts (STVE), aurait demandé à une employée de lui recoudre son pantalon de costume et de lustrer son argenterie pendant ses heures de travail, qu'il aurait demandé à des employés d'effectuer des petits travaux, comme tailler des arbres dans son jardin ou couper du bois pour la cheminée pendant les heures de travail, ou encore, que lui et ses collaborateurs travaillant pour la déchetterie auraient récupéré le cuivre et l'aluminium d'appareils usagés, les auraient stockés dans un container de la Ville de A._ et les auraient ensuite vendus à l'Espace récupération de la Praille; l'argent ainsi obtenu aurait été remis à X._. Le 20 août 2013, une instruction pénale a été ouverte contre X._, notamment, pour gestion déloyale des intérêts publics (art. 314 CP). Le rapport de l'enquête administrative concernant X._ a été versé à la procédure pénale. Par ordonnance du 17 août 2015, le Ministère public a classé la procédure dirigée contre X._, ordonné le séquestre et la confiscation, en particulier, de la pièce saisie figurant sous chiffre 15 de l'inventaire n°2260320130826 du 26 août 2013, refusé de lui allouer une indemnité à titre de réparation du tort moral et l'a condamné aux frais de la procédure arrêtés à 2'890 francs. Il a considéré que dans la mesure où X._ semblait crédible quand il déclarait avoir mis en place la pratique de récupération des métaux et du bois afin d'éviter des frais à la Ville de A._, l'intention de léser l'intérêt public, élément subjectif de l'infraction de gestion déloyale des intérêts publics, n'était pas réalisée, raison pour laquelle la procédure pénale concernant ces faits devait être classée (art. 319 al. 1 let. b CPP). S'agissant des travaux demandés par X._ à des employés communaux pour son propre profit, soit le fait de demander à des apprentis de tailler des arbres ou de demander à Y._ d'effectuer des travaux de couture et lustrer l'argenterie, la culpabilité du prévenu et les conséquences de ses actes devaient être considérées comme peu importantes, de sorte qu'un motif de renoncer à toute sanction en vertu de l'art. 52 CP étant réalisé, le classement était également ordonné s'agissant de ces faits (art. 319 al. 1 let. e CPP). Les frais devaient toutefois être mis à sa charge et une indemnité fondée sur l'art. 430 CPP devait lui être refusée dans la mesure où le recourant avait violé à plusieurs reprises et de manière fautive ses devoirs de service. B. Par arrêt du 9 juin 2016, la Chambre pénale de recours de la Cour de justice du canton de Genève a rejeté le recours formé par X._ contre l'ordonnance de classement du 17 août 2015. Elle a considéré que le comportement de X._ était propre à entraîner l'ouverture de la procédure pénale à son encontre et, dès lors, à engager des frais. L'ordonnance querellée était ainsi justifiée en tant qu'elle mettait les frais de la procédure à la charge de X._ et lui refusait toute indemnité pour ses frais de défense. La Chambre pénale de recours a par ailleurs déclaré le recours sans objet en tant qu'il concluait à la restitution de la pièce 15 de l'inventaire du 26 août 2013. Elle a condamné X._ aux frais de la procédure de recours, comprenant un émolument de décision de 1'000 francs. C. X._ forme un recours en matière pénale contre le jugement de la cour cantonale. Il conclut, avec suite de frais et dépens, à l'annulation du jugement attaqué et à sa réforme en ce sens que les frais de la procédure cantonale sont laissés à la charge de l'Etat et qu'une indemnité pour tort moral en 2'500 fr. avec intérêt à 5% dès le 23 août 2013 ainsi qu'une indemnité de défense de 52'920 fr. avec intérêts à 5% dès le 17 août 2015 lui sont allouées, sous suite de frais et dépens cantonaux. Il requiert également qu'il soit constaté que la cour cantonale a violé la présomption d'innocence.