楼兰建国的历史可以追溯到公元前3世纪，当时广大的西域地区特别是塔克拉玛干沙漠边缘的各绿洲上出现了许多小王国，楼兰就是其中之一。
楼兰之名最早见于汉朝，《史记·大宛列传》和《汉书·西域传》中记载了有关楼兰的点点滴滴。史料表明，楼兰王国在公元3世纪的汉初为月氏王廷所控制，到公元前2世纪时月氏王被匈奴打败后西迁，楼兰又为匈奴王廷所控制。
古代月氏部是中国历史上一支非常古老的部族，他们活动在甘肃西部的敦煌、祁连地区一带。汉时期，月氏部强盛了起来，其统治已占据了今甘肃西部大片地区，势力范围则已达到了中国北方草原和广大的西域地区，不仅楼兰等国为它所统治，就是当时的匈奴也曾在其统治之下。
匈奴世居草原，逐水草而迁徒，精于骑射，是一支能够迅速移动于几个纬度之间的劲旅，在古代东方及古代欧洲的历史发展上都有过重要的影响。头曼统治时，匈奴虽然已发展成为一支强大的政治、军事势力，但由于旧的所有制关系还没有完全消失，而新的生产关系和生产力的发展又很不完善，加上“东胡强而月氏盛”，中原地区又处于强大的秦王朝统治之下，因此，在相当长的历史时期内，匈奴势力一直被局限在阴山至河套以北一带。冒顿继位后，匈奴迅速走向鼎盛。
大约在汉文帝前元三年一前元四年(公元前177～前176)间，冒顿单于派右贤王率领骑兵攻打月氏，占据了月氏的全部领地，其子还把月氏王杀了，把月氏王的头盖骨做成了饮酒器具，月氏部与匈奴部结下宿怨。月氏部在匈奴的打击下，迁移到伊犁河流域，后来又在古代乌孙部的逼迫下，西迁至中亚的巴克特里亚地区(今阿富汗境内)。
当时月氏部有五翎侯部，其中的贵霜翎侯部强盛了起来，统一了月氏全部，在中亚地区建立了著名的贵霜王朝，成为中亚地区一个大国。
月氏西迁后，匈奴势力进入了古代西域地区。而楼兰国在摆脱了月氏统治后，又成了匈奴的附属，楼兰王向匈奴王廷称臣，定期向匈奴交纳赋税。
公元前140年汉武帝即位，为了驱逐匈奴，一方面便派使臣张骞出使西域，联络大月氏王夹击匈奴，另一方面他又采取军事手段，直接出兵攻打匈奴，逼迫匈奴退出河西地区，汉朝在河西地区建立了张掖、武威、酒泉、敦煌四郡，并在敦煌设立了玉门关和阳关，形成了西域地区汉匈直接对峙的局面。
公元前126年张骞从西域返回长安后，他向汉王朝报告他在西域各国的所见所闻，其中介绍了楼兰的情况，称：“楼兰，姑师邑有城郭，临盐泽。”“盐泽”，就是指今天的罗布泊。这说明楼兰在当时已经建立了城市。
自张骞出使西域后，汉朝就开辟了一条自都城长安经河西走廊，通向西方的道路。大批商贾和使者通过此道来往于东西方。而楼兰国正处西域地区最东边，又靠近汉朝的关隘，凡是东西往来的使者、商队在经过西域地区时必然都要进入楼兰国境内，加之罗布泊地区干旱缺水，途中又有白龙堆险道，过境者大都会在楼兰借歇。
楼兰在东西方交流中扮演了很重要的角色，给国内带来了经济和文化的繁荣，但随之负担也加重了，各种麻烦也增多，最后导致了楼兰与汉朝和匈奴的矛盾激化。
楼兰的负担是既要各旅途商队的物质供应，又要保护各个商队的安全，而在楼兰和姑师境内抢劫商队的事件时有发生。恶性抢劫事件增多后，汉朝和匈奴都对楼兰心存不满。
汉元封三年(公元前108年)，汉武帝决心要用武力去保护这条通道，就派大将赵破奴率领数万士兵去攻打姑师，同时又命令汉朝使节王恢率领骑兵攻打楼兰。王恢打进楼兰城，抓捕了楼兰王，楼兰王当即表示降服汉王朝。匈奴王廷知道了甚是不满，也发兵攻打楼兰，楼兰王无法抵抗，也对匈奴也表示臣服，并分别给汉朝和匈奴王廷各送一子当人质。而此后发生的一切致使楼兰国亡。
张骞从西域回汉后给汉武帝带来了一则有意思的新闻，称他在大宛见到一种不可思议的宝马，叫“汗血马”。此马为牡马与牝马所生，汗如鲜血，在战场上飞奔如风，为天下罕见。从前汉武帝的骑兵乘的是蒙古草原小马，尽管也算剽悍勇猛，但却不及汗血马，因此汉武帝非常想得到大宛的良马，以便迅速打败匈奴。汉太初元年(公元，前104年)汉武帝派壮士车令带了金子千两及一匹金马去大宛求马，不料被大宛王一口拒绝。消息传到长安，汉武帝为此大怒，遂决定派军远征大宛。公元前104年，汉武帝第一次出兵不利，又于公元前102年第二次派兵。汉军一直打到了大宛国，在围攻其国内贵山城时，大宛国内的贵族以抓绑了大宛王并送汉军汗血马3000余匹为条件，求汉军退兵。汉军杀了大宛王后回师长安。
在李广利二次攻打大宛时，匈奴曾企图在途中阻击汉军，但又怯于自己势单力薄，于是派骑兵到楼兰，命令楼兰王拦截汉军的后队。
此事被当时驻扎在玉门关的汉军任文知道，回报给了汉王廷，汉王廷当即下令任文抓捕楼兰王，楼兰王一副无奈之态，对汉王廷说：“小国在大国间，不两属无以自安，愿徙国人人居汉地。”汉武帝听后，认为楼兰王说的是实话，就放楼兰王回国，但提出要楼兰王及时向汉朝通报匈奴的动向。汉征和元年楼兰老王死了，新王当政，汉朝仍要求新王送一子到汉王廷当人质，楼兰王应允。新王死后，匈奴先得到消息，就派在匈奴的楼兰国质子马上返回楼兰接王位，楼兰新王因年轻时在匈奴王廷生活，明显地倾向于匈奴，对汉朝入朝之请置之不理。
在他任王期间，先后发生了几起杀害汉大臣的事件，并还数次抢劫杀害安息使臣和大宛国的使臣等，汉王廷对此极为不满。汉武帝去世后，汉昭帝即位。汉昭帝派了骏马监傅介子在去大宛的途中，路过楼兰、龟兹时，向他们提出质问。傅介子到达楼兰后，即责问楼兰王，楼兰王表示以后不再发生此事，并讨好地告知傅介子说匈奴使者已到龟兹国去了。傅到龟兹国后，得知匈奴使者已去了乌孙，傅介子就决定先去大宛国。当他从大宛国回去时，在龟兹国得知匈奴使者也已从乌孙回到了龟兹，傅介子当即决定率领其随从、士兵包围了匈奴使者，并杀死了他们。傅介子回到长安后，汉王朝封他为平乐监。
汉昭帝元凤四年(公元前77年)傅介子向大将军霍光建议：楼兰、龟兹都是小国，但他们对汉朝的态度数次反复无常，应当给予惩罚，并表示自己愿意亲自去解决。大将军霍光建议他先去解决楼兰。
于是傅介子带了随从士兵和许多金银财物，来到楼兰，要求见楼兰王。可楼兰王始终不露面。傅介子称自己带了许多礼物本来是要送给楼兰王的，如楼兰王一直不见我，我只好离开楼兰国到别处去了。
贪婪的楼兰王听到消息后立即在王宫设宴宴请傅介子一行。就是在这场宴会结束之际，一把锋利的钢刀从背后刺人楼兰王的胸部，楼兰王当即死去。傅介子在楼兰王宫当众宣布是楼兰王辜负了汉王朝，汉天子派我来诛杀他，并称王死后就由王弟尉屠耆为新王，楼兰国更名为鄯善国。在漩涡中挣扎了300年的西域小国楼兰从此退出了历史舞台。