Secondo fonti assire del VII secolo aC, Nicosia era una città di nome Ledra. Nel 300 aC circa, il figlio del re egiziano Tolomeo, Lefkos, ricostruì la città, e il suo nome è immortalato nel moderno nome locale di Lefkosa (turco) o Lefkosia (greco). Nicosia è il nome francese della città e si pensa che sia apparso alla fine del 1100. Il nome è usato principalmente da stranieri.
Nicosia e' la capitale di Cipro ed è attualmente la città più grande e più densamente popolata dell'isola. Essa inoltre è oggi divisa nei settori turco e greco da un confine noto come la linea verde, che corre in direzione est-ovest.
Nel 1191, Riccardo Cuor di Leone, sulla strada per la Terra Santa durante la Terza Crociata, catturò l'isola come risposta alle azioni contro la sua flotta da parte del Re di Cipro. Fu a Cipro che Riccardo sposò Berengaria di Navarra, che fu scelta come sua moglie da sua madre, la regina Eleonora d'Aquitania. Cipro rimase sotto il dominio di Riccardo per solo un anno.
Nel 1192, la vendette ai Cavalieri Templari che governarono l'isola da Nicosia. La vita sotto i templari era dura, e presto incapparono nell'odio degli isolani. Incapaci di tenere l'isola con la forza, i Templari supplicarono Riccardo di riprendersi l'isola che la vendette rapidamente a Guy de Lusignan che aveva perso il suo regno di Gerusalemme.
Nicosia è stata la capitale di Cipro da allora, e prosperò durante l'era dei Lusignano. Furono costruite chiese e palazzi e la citta' crebbe per dimensioni e popolazione. Questo periodo importante della storia della città terminò nel 1489 quando i Veneziani conquistarono Cipro.
I Veneziani demolirono la maggior parte dei monumenti dei Lusignano, comprese chiese e palazzi, e usarono la muratura per fortificare la città contro i tentativi di invasione ottomana. Nel 1567, poco prima della conquista di Cipro da parte degli Ottomani, i Veneziani iniziarono a costruire nuove mura protettive al posto delle antiche mura dei Lusignano che circondavano la città, in modo da poter difendere Nicosia. Un famoso ingegnere veneziano, Guillio Savorignano disegnò i piani per le mura. Dovevano avere una circonferenza di tre miglia, 11 bastioni, ognuno simile a un castello e tre porte. I resti delle mura circondano ancora oggi la città vecchia. Le tre porte erano la porta di Kyrenia a nord, la porta di Famagosta a est e la porta di Paphos a ovest. La Porta di Kyrenia è oggi ancora intatta.
Per costruire le mura, i Veneziani demolirono case, palazzi, monasteri e chiese al di fuori della circonferenza di tre miglia della città, e usarono la loro pietra nella costruzione delle mura. Di conseguenza, non vi è alcuna traccia dell'insediamento medievale che preesisteva. Tuttavia, i loro sforzi non impedirono all'isola di cadere nelle mani delle forze dell'ammiraglio ottomano Lala Mustafa Pasha nel 1570. Questo evento impedi' il completamento delle mura.
Dopo la conquista, la città acquisì nuovo vigore e vennero fondate moschee, bagni e altre istituzioni per soddisfare le esigenze dei suoi nuovi padroni e iniziò una nuova attività edilizia.