Faits: A. Le 31 octobre 2000, A._ et B._ ont acquis l'immeuble édifié sur la parcelle 300 de la commune de Genève, à l'adresse X._. Depuis le 14 août 2003, l'immeuble est soumis au régime de la propriété par étages (PPE). B. Par arrêté du 9 février 2010, le Département cantonal des constructions et des technologies de l'information (ci-après: le DCTI) a autorisé l'aliénation d'un appartement de deux pièces situé dans l'immeuble précité, à savoir le n° 5.05, à C._. Par arrêté du 15 novembre 2010, le DCTI a autorisé la vente de l'appartement de deux pièces n° 3.07 au profit de D._. Par arrêté du 1er décembre 2010, le DCTI a autorisé la vente de l'appartement de deux pièces n° 4.04 à E._. C. L'Association genevoise de défense des locataires (ci-après: l'Asloca) a recouru contre ces autorisations auprès de la commission cantonale de recours en matière de constructions, remplacée par la commission cantonale en matière administrative et devenue depuis le 1er janvier 2011 le Tribunal administratif de première instance (ci-après: le TAPI). Après avoir procédé à l'audition des parties, le TAPI a admis les recours et annulé les trois autorisations précitées le 7 octobre 2011. Par arrêt du 5 juin 2012, la Chambre administrative de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours de A._ et B._ contre le jugement du TAPI du 7 octobre 2011. Elle a considéré en substance que l'intérêt public à la protection du parc locatif, prépondérant en période de pénurie de logements, l'emportait sur l'intérêt privé des propriétaires à vendre leurs appartements loués et des locataires à les acquérir. D. Agissant par la voie du recours en matière de droit public, A._ et B._ demandent au Tribunal fédéral d'annuler l'arrêt de la Cour de justice du 5 juin 2012, de dire que les recours de l'Asloca devant le TAPI étaient irrecevables, voire infondés, et de rétablir les autorisations litigieuses. Les recourants reprochent pour l'essentiel à la cour cantonale d'avoir mal établis les faits et appliqué arbitrairement le droit cantonal. La Cour de justice s'en rapporte à justice quant à la recevabilité du recours et persiste dans les considérants et le dispositif de son arrêt. Le DCTI propose l'admission du recours et l'Asloca conclut à son rejet. Les recourants ont répliqué; ils persistent intégralement dans leurs conclusions.