Tarkovski’nin ilk uzun metrajlı filmi İvan’ın Çocukluğu oldu. 1962 yılında tamamlanan film Tarkovski’ye çok geçmeden uluslararası bir ün sağladı.

İvan’ın annesi rolünü Tarkovski’nin karısı İrma Rausch’un oynadığı bu filmde, ailesinin savaşta kaybeden bir çocuğun cephede geçen yaşamı sergilenir. Vladimir Bogomolov’un 1957’de yazdığı İvan adlı kısa öyküden uyarlanan filmin senaryosu Mikhail Papava tarafından yazıldı. Büyük ölçüde Dinyeper Nehri yakınlarındaki Kaniv’de çekilen filmde, cennetsi düş sahneleriyle gösterilen İvan’ın yitik çocukluğu savaşın yarattığı yıkımla karşıtlık içerisindedir.

Rusya’daki ilk resmî gösteriminde büyük ilgi toplayan bu film uluslararası alanda da büyük bir başarı kazandı. 1962 Film Festivali’nde Altın Aslan Ödülü’nü kazanan film aynı zamanda İngmar Bergman, Sergei Parajanov ve Krzysztof Kieslowski gibi ünlü sinemacılardan ve Jean Paul Sartre gibi entellektüellerden çok büyük övgüler aldı.

Bu başarıdan sonra Tarkovski ikinci uzun metrajlı filmi Andrei Rublev üzerine çalışmaya başladı. Tarkovski ve sinema okulundan arkadaşı senarist Andrei Mikhalkov Konçalovski filmin çekimi başlamadan önce iki yıl boyunca senaryo üzerinde çalıştılar.

Ortaçağ Rus keşişi ve ikon ressamı Andrei Rublev’in mücadeleleri hakkında olan bu film aynı zamanda barbarlık karşısında sanatın zaferini, Andrei Rublev’in ruhanî yolculuğunda kişileşen insanlığın ruhanî doğasının bir yönü olarak sanatın işlevi ve sanat fikrinin sıradan insanların yaşamlarıyla derinden bütünleşmesi anlatıyor. Sovyet hükümeti filmin yüzeyinin hemen altında yatan alegorik eleştiriyi gözden kaçırmadı ve Andrei Rublev 1971 yılına kadar Sovyetler Birliği’nde gösterilmedi. Ama bu sırada eleştirmenler filmi bir şaheser olarak nitelediler. 1969 yılında film Cannes Film Festivali’nde yarışma dışında gösterildi ve Federation Internationale de la Presse Cinematographique (FIPRESCI) ödülünü aldı. 1971’de ise Fransız Sinema Eleştirmenleri Sendikası tarafından en iyi yabancı film seçildi.

Tarkovski filmi siyah-beyaz olarak çekti ama filmin epilog bölümünde, Andrei Rublev’in 15. yüzyılda yaptığı gerçek ikonalar gösterilirken renkli film kullandı. Filmin bu şekilde gerçekliğe yerleştirilmesi hikayeyi etkili bir şekilde sonlandırmaktadır.

Andrei Rublev üzerine çalışırken, Tarkovski filmdeki meczup kadını oynayan karısından ayrıldı ve oyuncu Larissa Pavlovna Yegorkina ile birlikte yaşamaya başladı. Tarkovski ve Yegorkina 1970’de evlendiler ve aynı yıl çocukları Andrei doğdu.