Faits: A. Par jugement du 8 mai 2013, le Tribunal correctionnel du canton de Genève a condamné A._ pour vol en bande et séjour illégal à une peine privative de liberté de 10 mois, sous déduction de 150 jours de détention avant jugement, peine complémentaire à celles prononcées les 2 et 16 janvier 2013. Il a également renoncé à révoquer le sursis octroyé le 4 mai 2009 (peine pécuniaire de 80 jours-amende à 30 fr.) dont il a prolongé le délai d'épreuve de 2 ans et la libération conditionnelle accordée le 25 septembre 2012 (solde de la peine et délai d'épreuve de 2 ans et 2 mois) dont il a prolongé le délai d'épreuve d'un an et un mois. B. Par arrêt du 20 septembre 2013, la Chambre pénale d'appel et de révision de la Cour de justice genevoise a admis l'appel formé par le Ministère public. Elle a révoqué la libération conditionnelle octroyée le 25 septembre 2012 à A._, prononcé une peine d'ensemble de 2 ans et 6 mois, sous déduction de la détention avant jugement, dit que cette peine était complémentaire à celle prononcée le 16 janvier 2013 et confirmé le jugement de première instance pour le surplus. En bref, il en ressort les éléments suivants. Entre le 2 et le 9 décembre 2012, A._ a, de concert avec B._ et C._, dérobé la monnaie contenue dans plusieurs horodateurs à Genève, pour un montant total de 40'932 fr. 15. Son rôle consistait à regarder ses deux comparses voler l'argent, le récupérer et le cacher dans un box proche de son appartement aux fins de changer la monnaie en billets, ce dont il s'occupait également. Il a en outre séjourné illégalement en Suisse du 1 er au 10 décembre 2012. A._, ressortissant roumain, est issu d'une famille de six enfants. Il s'est beaucoup occupé de sa mère décédée d'un cancer en 2006. Il a suivi un parcours universitaire, avec obtention d'une licence, ainsi qu'une école hôtelière. Après une faillite subie en 2006, il a travaillé dans la société de son père comme technicien en approvisionnement puis comme directeur marketing. Il souhaitait travailler dans cette entreprise, un poste vacant étant disponible. Son père malade avait l'intention de se retirer peu à peu des affaires. A._ a été condamné à quatre reprises : le 4 mai 2009, par le Tribunal de police genevois pour encouragement à la prostitution et séjour illégal, à 80 jours-amende à 30 fr., avec sursis pendant 4 ans; le 27 mai 2009, par la Cour correctionnelle genevoise, pour infraction à la LStup, à une peine privative de liberté de 6 ans et 6 mois; le 2 janvier 2013 par le Ministère public genevois pour incitation à l'entrée, à la sortie ou au séjour illégal, à une peine pécuniaire de 40 jours-amende à 30 fr., avec sursis pendant 3 ans et le 16 janvier 2013, par le Ministère public fribourgeois, pour vol d'importance mineure et faux dans les certificats, à une peine privative de liberté de 30 jours et une amende de 300 francs. Par jugement du 25 septembre 2012, le Tribunal d'application des peines et mesures (ci-après : TAPEM) a prononcé la libération conditionnelle de A._ de la peine privative de liberté de 6 ans et 6 mois prononcée le 27 mai 2009 et fixé le délai d'épreuve à 2 ans et 2 mois, soit l'équivalent du solde de la peine. C. A._ forme un recours en matière pénale devant le Tribunal fédéral contre l'arrêt du 20 septembre 2013. Il conclut, avec suite de dépens, principalement à son annulation et à la confirmation du jugement de première instance, subsidiairement au renvoi de la cause à l'autorité inférieure. Il requiert par ailleurs l'assistance judiciaire.