Название XIX века.
Улица названа по песчаной почве этого района.
Местность, где находятся Песчаные улицы, вошла в состав города в 1917 году. Ранее это было старинное село Всехсвятское, известное по документам с 1498 года. Оно переменило немало владельцев: в XVII веке принадлежало Троице-Сергиеву монастырю, в XVIII веке было взято в казну. Через Всехсвятское прошел Петербургский тракт, и это способствовало его расширению и обогащению.
Всехсвятское считалось околицей Москвы.
«…Любезный читатель!.. Вот уже Всехсвятское, – заканчивает А.Н. Радищев свое повествование о путешествии из Петербурга в Москву. – Если я не наскучил тебе, то подожди меня у околицы: мы повидаемся на возвратном пути. Теперь прости. Ямщик, погоняй. Москва! Москва!»
А Пушкин так комментирует эти строки: «Москва! Москва! – восклицает Радищев на последней странице своей книги и бросает желчью напитанное перо, как будто мрачные картины его воображения рассеялись при взгляде на золотые маковки Москвы белокаменной. Вот уже Всесхвятское…».
Во второй половине XVIII века, несмотря на то, что Всехсвятское находилось далеко за пределами административной границы Москвы, за заставой Камер-Коллежского вала, фактически оно уже являлось частью города.

В районе Сокола. Конец 1930-х гг.
Тогда была очень популярна песня, даже вошедшая в самую известную комическую оперу Аблесимова «Мельник – колдун, обманщик и сват», и в ней утверждалось, что Всехсвятское находится совсем рядом с Пресненскими прудами – любимым местом гуляний москвичей:
Вот спою какую песню:
Ходил молодец на Пресню,
Под вечерок,
Путь недалек;
Ходил молодец на Пресню
Из Всесвятского села,
Под вечерок,
Путь недалек.
В XIX веке несколько улиц села Всехсвятского назывались Песочными, или Песчаными. После революции обжитая местность вокруг Всехсвятского стала быстро застраиваться, в 1921 году возник кооперативный поселок «Сокол», существующий до сих пор. Особенно значительное строительство велось в конце 40-х – начале 50-х годов. Возникали новые улицы и переулки, они были также названы Песчаными с прибавлением порядкового номера: с 1-й по 7-ю улицы, и с 1-го по 5-й переулки.
В 1965 году 2-я Песчаная улица была переименована в улицу Георгиу-Дежа. Г. Георгиу-Деж (1901—1965) – деятель международного коммунистического и рабочего движения, Генеральный секретарь Компартии Румынии.