在塔克拉玛干绿洲的居民当中，从祖父到孙子，到所有能够记忆的人们当中，一直流传着，并将长期流传下去关于埋葬在沙子里面的古代市镇的奇怪传说。据传，在沙丘中间埋有大量金银和其他财宝。这些东西对于那些敢于向沙漠上的自然和超自然的恐怖进行斗争的人们来说，是随时可以往取的。公元1875年，一个曾经在罗布泊附近的盐碱沼泽地带当过吉尔吉斯部落的牧羊人的人，据说他从远处看见过一个被湮没的城市，曾经作过生动的叙述。他说：
“城垣耸立在芦苇丛中，整个城市就隐藏在这些芦苇的里边。
我没有走到里边去，这是从附近的沙脊上，可以很清楚地看清它的城垣。因为它四周围绕着泥塘，草丛中有毒虫和长虫，所以我没敢进去……所有确实进去过的人，几乎都因为经受不住其中储藏着的财宝的引诱，而大都死在里面。这是众所周知的事实……可能你会不相信，但这里的人，都知道我说的话是真的。有数以百计的卡尔迈克人（Kalmaks）走进废墟中的寺庙里去祭祀神仙……在这里神像四周的架子上，摆满了巨大的光辉夺目的明珠、宝石和无数的金银元宝。但是谁也没有权利从这里拿走其中的任何一样东西。这对罗布泊人来说，是家喻户晓的。”
发表在一份印度政府官方公报上的他的一篇叙述继续报道说，有一个卡尔迈克人到庙里去祭祀神仙，但由于他财迷心窍，经不起诱惑，便偷了两个金元宝藏在口袋里，他还没走多远，突然感到非常疲乏，于是躺下来就睡着了，当他醒过来的时候，发现他的元宝不见了。因此他又到庙里，打算再多拿一些。这次使他惊异的是，他第一次所拿的两个元宝，端端正正地仍旧放在原处。
故事继续报道说，这可简直把他吓呆了。于是他赶紧跪在神像前，磕头如捣蒜似的请求宽恕。那个神像笑了，这是警告他说，今后再不许盗窃圣物。这使他大为欣慰。
另外一种传说则是有关这些城市原先是如何毁灭的事情。一般地说，这是对于居民罪恶的一种惩罚。公元16世纪，穆斯林历史学家默扎·海达（Mirza Haidar）叙述过罗布泊附近的市镇卡塔（Katak）是怎样遭受这种命运而毁灭的。他说，当时只有一个伊斯兰教的学者和一个报呼祷告时刻的回教徒，由于信仰虔诚，得以免于被席卷而来的流沙所吞噬。当报呼祷告时刻的那个教徒正在进行晚祷时，天便开始下起沙子了。除了清真寺以外，整个市镇很快就慢慢地消失得无影无踪。这个惊慌失措的教徒从尖塔的顶端向下看时，发现四周的土地一直在迅速地往上升。于是他赶快结束了祷告，迅速地跳到离他只有几英尺的沙子上。他和那个学者认为，“远远地离开愤怒的上帝．是一个聪明的主意”。于是他们两人就飞快地逃走了。默扎·海达接着说：“卡塔这个城市就这样一直被沙漠掩埋到今天。”
有一些关于这类罪恶之地的故事，其流传的时间比上边提到过的还要早一些。那时候，佛教在丝绸之路沿线上仍很流行。公元7世纪，伟大的圣地探险家佛教徒玄奘（后来被斯坦因爵士尊之为护法圣徒）谈过另一个市镇的故事。那就是在若干世纪之前，由于当地居民们忽视了他们在宗教上所应尽的责任，结果那个城镇就被沙漠风暴湮没了。玄奘说，一阵巨大的风刮起来了，“第七天的傍晚，正是昼夜交替的时候，沙土开始降落了”。不多一会，他叫做霍落落卡（Ho-lo-lo kia）的这个市镇，就湮没在巨大的沙堆之中。玄奘接着说：“附近国家的国王以及远处掌权的人们，曾不止一次地打算挖掘这个沙堆，拿走湮没在里边的珍宝。但是当人们刚一到达它的近旁时，突然就刮起一阵狂风，吹得滚滚黑云从四处围绕起来，接着这些人也就消失了。”据说，被埋藏在塔克拉玛干沙子底下的市镇，为数约三百左右。
但是，近处的一个国王，却并没有被玄奘的“狂风”或者其他有关沙漠中的恐怖故事所吓倒。他决心从湮没的城市中获得珍宝。伟大的亚洲学者和旅行家奈伊·伊莱亚斯（Ney Elias）于1895年在他的著作中，把他所描绘的东西说成是“前所未有的对古代遗址的有计划的发掘”。这一次是穆斯林国家喀什的暴虐酋长默扎·阿拔·贝卡（Mirza Aba Bakr）用他的奴隶劳力来发掘的。
（他也的确得到了一个很坏的结局——在睡梦中，他的头被砍掉了。）生活在同时代的默扎·海达对有关这个酋长在和阗地区猎宝的经过曾经作过叙述。伊莱亚斯在给他的著作的翻译本所作的序言中作了这样的结论：“我们可以推想，每一件具有内在价值的东西几乎都被挖掘出来了，但是许多具有文物价值的东西都遭到了破坏。所以在未来的时日里，当有相当文化修养的探险者前来调查这个废墟而同时又发现他们所付出的代价是得不偿失时，那他们对默扎·阿拔·贝卡的贪婪野心所给予他们的失望，会感到不胜遗憾。”
以上这些话只是在斯坦因越过冰雪封途的喀喇昆仑，朝向塔克拉玛干出发的前五年写的。这一次是他在该地进行三次大量盗窃中的第一次。他的三次远征都明确地驳斥了伊莱亚斯的那种说法。伊莱亚斯绝不会知道这一点，因为他在1897年就死了。那时候斯坦因还正在计划着他的第一次旅行。
虽然在伊莱亚斯时代，还没有一个欧洲旅行家曾经去发掘过这些湮没了的城市中的任何一个，可是若干年来西方学者们一直认为它们有存在的可能性，和传说不同。第一个可靠的证据是在1865年，由一个当地旅行者提供出来的。他是一个名叫穆罕默德·衣·哈密德（Mohamed-i-Hameed）的印度雇员。他奉英政府的秘密使命，被派到喀喇昆仑去探索塔克拉玛干的一些绿洲的情形。
当时这个地区还是人们闻所未闻的。之所以派他去，是因为加尔各答和伦敦当局考虑到，若是派遣英国官员（即使是乔装打扮）进入介于俄印之间的中国这块落后的没有设置警察的地方，无论从政治上和个人安全上来说，都是非常危险的。另一方面，他们一直在担心沙皇俄国对于印度的威胁并急切地要掌握这里各条路线的准确测量记录。这是因为横跨这个无人地区的那些路线很有可能被入侵的军队所利用。
在19世纪60年代，负责绘制整个英属印度以及印度以外各地的地图的印度测绘局的T．G．蒙哥马利上尉，想出一个明智的解决办法——利用印度籍的雇员。他在1866年5月14日向在伦敦的英国皇家地理学会宣读了他写的一篇报告。他在说明写在这篇报告里的想法时，他告诉他的听众说：“当我在拉达克（Ladakh）时，我注意到，印度人可以自由地来往于拉达克与叶尔羌之间，这使我意识到，有可能利用他们来进行探测。如果能找到一个很机警伶俐的印度人，那他就不难在商品中夹带少数小型的仪器，进入这个地区。我想，他借着这些仪器的帮助，有可能在地理方面作出很大的贡献。”
旁遮普的副总督同意供给费用，成立只由一个印度人组织的远征队，进入中国的中亚。于是这个已经有过许多次路线测量经验的穆罕默德·衣·哈密德雇员就被选中了。经过更进一步的训练之后，他带着为了达到这个目的而特别设计的秘密测量仪器，被派往叶尔羌。临行前给他准备了一条喜马拉雅旅行者所时常携带的顶端带有铁尖的普通手杖，来替代通常在测量时所使用的棱柱形的罗盘架子。但是这个手杖的顶端做得比平常用的稍微大些，同时还把顶端切平，使罗盘能够安放在它的顶上。用这个手段，蒙哥马利解释说：“一种稳妥可靠的观察，就可以在毫无困难的情况下，顺利地进行，而且也不容易引起猜疑。”这个雇员所携带的其他仪器还有，在夜间照看六分仪时所需要的用马口铁造的小型提灯，为煮沸温度计（计算高度）用的一把铜水壶和一盏油灯。这些东西都是造成最小型的。到那里去进行探测，正如这个雇员和他的间谍主子们所熟知的那样，几乎是意味着要死于蒙哥马利所说的出没于那条路上的吉尔吉斯游牧民族之手。他所说的“那条路”，指的就是从拉达克越过喀喇昆仑，到中国土耳其斯坦的叶尔羌所要走的那条可怖的、沿途被白骨点缀着的道路。
公元1863年6月2日，穆罕默德离开克什米尔，前往英国势力的最后前哨基地拉达克。他带着运输队从那里越过蒙哥马利所描绘的“世界上最高的国家”，在三个半月之后，到达了叶尔羌。
在这里他停留了六个月，这时他的所有时间都是用在使用他的仪器为蒙哥马利进行秘密的探测工作上，同时他还记录了他所见的每一件事情。后来，在1864年3月末，一个穆斯林朋友警告他说，当地的中国官吏对他的行动已经发生怀疑，并且还进行了调查。于是，这个雇员把与他有牵连的装备先运走之后，便神不知鬼不觉地从叶尔羌溜走了；经由喀喇昆仑要隘，返回了拉达克。
大概是由于旅途的劳顿，这个雇员和另一个旅伴都得了病，并正在家乡在望的时刻，他俩都死了。最初人们都认为，他们的死可能是由于遭到了中国特工人员的毒手。但是，经过当时正在这个地区进行测量的蒙哥马利的一个同僚、非军职助理威廉·约翰逊的调查，最后证明他不是被中国人谋害的。虽然这个雇员的一些可以变卖的东西已经失踪了，可是他在进行他的秘密使命的整个过程中，极其小心谨慎地保存下来的那些珍贵的记录，则被约翰逊发现了，并交给了蒙哥马利。
印度测绘局所主要关心的不但是这个雇员对于在该地区的俄国人的活动所作的观察报告，而且还有在他的记录中所记载的有关地形地貌的情报。然而，蒙哥马利还在其中无意地发现了一份很能引起人们兴趣的记录。这份记录根据可靠的来源第一次证实了过去为人们所认为纯属空想出来的传说。
应当承认，他所叙述的细节，是并不十分充足的。但是这个雇员的工作，并非是从事考古学的研究。“这个省的古都和阗，在很早以前就为流沙所湮没。”这是蒙哥马利在报告时引证雇员的记录簿中的话。然而，从当地居民提供的资料来看，在沙暴过后，一些古老的房屋又露出来了，而且“他们还时常从沙子底下挖掘出许多被埋藏的东西”。这个雇员由此推断：“当时沙暴一定是来得极突然，致使居民还没有来得及搬走他们的财产……这个城市就被掩埋了。”他并没有用一般的渲染词藻说什么神的惩罚呀，无价之宝呀，保护之神呀等等。他的叙述虽然是道听途说的，但听起来，多少像是真实的。