Faits: A. Le 15 janvier 2008, X._ a été inculpé d'escroquerie et de tentative d'escroquerie. Par ordonnance du 21 avril 2010, la Chambre d'accusation genevoise a prononcé un non-lieu en sa faveur. Cette décision a été confirmée par la Cour de cassation genevoise le 2 novembre 2010. Le 1er juin 2012, X._ a saisi le Tribunal d'application des peines et des mesures du canton de Genève (TAPEM) d'une requête en indemnisation, concluant après réduction de ses prétentions à l'allocation de 34'986 fr. 02 plus intérêt à 5 % l'an dès le 21 avril 2010, montant correspondant à ses frais de défense. Par jugement du 27 juillet 2012, le TAPEM a jugé la requête irrecevable. B. Par arrêt du 12 octobre 2012, la Chambre pénale d'appel et de révision de la Cour de justice du canton de Genève a rejeté le recours de X._. En bref, elle a considéré que ses prétentions en réparation du dommage relatif aux frais de défense étaient régies par l'ancien code de procédure pénale genevois (CPP/GE) et non par le CPP et que l'action entreprise par X._ était tardive dès lors que le délai de péremption de l'art. 380 al. 4 CPP/GE était échu. C. X._ forme un recours en matière pénale au Tribunal fédéral contre cet arrêt, concluant, sous suite de dépens, à sa réforme en ce sens que l'Etat de Genève est condamné à lui verser 34'986 fr. 02 plus intérêt à 5 % dès le 21 avril 2010. La cour cantonale et le ministère public concluent au rejet du recours. 