Лунные космические станции Королёва, одобренные в марте 1958 года, в первые месяцы осуществления программы начинались с разочарований, отсрочек и неудачных запусков. Неисправности двигателя сопровождались ожесточенными спорами о его оптимальной конфигурации между Королёвым и Валентином Глушко, главным конструктором советских ракетных двигателей. 23 сентября 1958 года состоялся неудачный запуск лунного космического корабля, когда стартовый ускоритель развалился всего через несколько секунд после взлета. Таким же неутешительным был запуск 11 октября, произведенный сразу после первой годовщины «Спутника-1». Следующий досадный провал последовал 4 декабря, который еще больше усилил ощущение тщетности предпринимаемых действий на Байконуре.
Запуск 2 января 1959 года «Луны-1» (названной «Мечта») оказался, наконец, успешным. Конструктивно измененная Р-7 успешно подняла лунную исследовательскую станцию, преодолев земное притяжение, и вывела ее на исторический курс по направлению к Луне. Достигнув второй космической скорости, космическая станция отделилась от третьей ступени. На отметке 112 000 км космический корабль выпустил килограммовое облако паров натрия, создав обширный оранжевый шлейф. Это струящееся пятно света с яркостью звезды шестой величины было видно над Индийским океаном, являясь визуальным подтверждением лунной траектории.
«Луне-1» предназначалось стать первым искусственным объектом, достигшим поверхности Луны, но исторической встречи с небесным телом не произошло: спустя 34 часа после запуска космический корабль прошел на расстоянии примерно 5900 км от цели. Тогда «Луна-1» вышла на орбиту вокруг Солнца, провозгласив еще одно «впервые» советской космической программы. Хотя «Луна-1» не имела на борту никаких фотокамер, она была оснащена очень сложной аппаратурой, включая детекторы, которые измерили радиационный пояс Земли, чем продемонстрировали отсутствие магнитного поля у Луны, а также обнаружили солнечный ветер — мощный поток ионизированной плазмы, испускаемый Солнцем. «Луна-1» явилась настоящим событием, которое перенесло арену соперничества между Советским Союзом и Соединенными Штатами далеко в космическое пространство.
2 сентября 1959 года Советский Союз запустил «Луну-2». Это была первая советская космическая станция, достигшая Луны. Как и при запуске первой лунной космической станции, было выпущено оранжевое облако газа, призванное не просто отметить траекторию космического корабля, но и изучить газ в состоянии невесомости в условиях открытого космоса. Лунная космическая станция «Луна-2» с полезным грузом весом 363 кг достигла лунной поверхности через полтора дня полета, врезавшись в лунную поверхность в точке, восточнее Моря Спокойствия. При соприкосновении с поверхностью станция разбросала несколько металлических вымпелов, чтобы отметить место исторического падения. На металлических вымпелах была простая надпись: «СССР. Сентябрь 1959». Попасть в Луну, огромный, но быстро движущийся объект, расположенный на расстоянии почти 320 000 км от Земли, было для того времени впечатляющей демонстрацией меткости. Советская лунная ракета олицетворяла собой совершеннейшую систему наведения и навигации, позволившую достичь этой цели.
Самая внушительная лунная космическая станция «Луна-3» оторвалась от Земли 4 октября 1959 года, во вторую годовщину «Спутника-1». Этот запуск представлял собой самый амбициозный шаг, когда-либо совершенный Королёвым и его командой инженеров и ученых. Взлетев с Байконура, «Луна-3» вышла на сильно вытянутую эллиптическую орбиту вокруг Земли, а потом — на траекторию в форме восьмерки, которая вывела ее на облет вокруг Луны, и затем — назад по направлению к Земле. Подойдя на расстояние 6080 км от Луны, «Луна-3» развернулась к ее теневой стороне (всегда спрятанной от обозрения с Земли), чтобы сфотографировать ее. 7 октября телевизионная система, установленная на станции, сделала 29 фотоснимков, охватывающих 70 % обратной стороны Луны. На это потребовалось 40 минут. Затем 18 октября изображения были отсканированы для передачи на наземные станции в оптимальный момент, когда «Луна-3» приближалась к Земле во время своего обратного полета. Русские сотрудничали с британцами, которые позволили с помощью знаменитого 250-футового радиотелескопа в Джодрелл Бэнк записать изображения, посланные с космического корабля «Луна-3». Это была примечательная просьба, учитывая секретность, окружавшую все производимые в Байконуре запуски. Обработанные изображения — первые изображения темной стороны Луны — были невысокого качества, но они позволили составить карту и провести научный анализ до тех пор скрытых особенностей лунной поверхности.