До Второй мировой войны в тогдашнем немецком Мемеле была небольшая православная община, которая насчитывала лишь 30-40 человек. Редкие службы осуществлялись приезжими священниками. С 1937 года клайпедский молитвенный дом духовно окормлял клир векшняйской Свято-Сергиевской церкви: в портовый город попеременно наведывались священники Александр Чернай и Виктор Курилович. Во время Второй Мировой войны молитвенный дом, где собирались верующие, был разрушен. В 1947 году православная община Клайпеды увеличилась за счет приехавших сюда русских, создававших главный морской порт Литвы и число верующих возросло до тысячи. Клайпедская община была в то время едва ли не самой крупной в республике. Общину возглавил протоиерей Иоанн Левицкий. О. Иоанн родился и вырос в Литве. Будучи уже в священническом сане он пережил тяготы двух Мировых войн. Руководство епархии не раз посылало этого батюшку на сиротствовавшие приходы. И вот теперь он взялся за восстановление православной общины в портовом городе. Вместе со всеми верующими о.Иоанн ходатайствовал об открытии православного храма в городе. Власти города долго противились. Но все-таки в декабре 1947 года общине верующих было передано здание бывшей лютеранской кирхи. Полгода ушло на то, чтобы приспособить его для проведения богослужений. На конных повозках в Клайпеду привезли иконостас, из закрытой властями православной церкви в латвийской Лиепае. Новый православный храм был освящен во имя Всех святых, в Земле Русской просиявших. Долгие годы наряду с православными богослужениями во Всехсвятском храме совершались также лютеранские службы.
Первым настоятелем храма стал священник Феодор Ракецкий. 28 декабря 1947 года он совершил первую литургию. Массовая депортация в 1948 году жителей Литвы в отдаленные области Советского Союза не оставила равнодушным о. Фёдора и за неосторожные высказывания его, по доносу информатора, арестовали в июне 1949 года. Священника осудили по статье 58 на десять лет исправительно-трудовых лагерей «за антисоветскую пропаганду». Освобожден о. Феодор Ракецкий был только в 1956 году. Настоятелем храма Все святых с 1949 года был протоиерей Николай Недвецкий.
31 октября 1954 года произошло замечательное событие в истории клайпедской церкви – была освящена храмовая икона «Всех святых, в Земле Русской просиявших». Ее создание было задумано и осуществлено настоятелем о. Николаем в трудное для церкви время, когда даже просто напечатанные иконы были редкостью. Он кропотливо собирал изображения русских святых, начиная от князя Владимира, чтобы потом художник мог изобразить их на большой общей иконе. Протоиерей Николай Недвецкий служил настоятелем в течение 35-ти лет, вплоть до своей кончины в 1983 году. Долгие годы во Всехсвятском клире состоял вторым священником протоиерей Николай Гирилович, переведенный из Шяуляй в 1957 году. Затем здесь служили иерей Александр Прокофьев (с 1984 года), игумен Феофан. В 1986 году главой клайпедской Всехсвятской общины назначили архимандрита Антония (Буравцева). В середине 60-х годов ХХ века после рукоположения во иеродиакона в Троице-Сергиевой лавре он в течение пяти лет служил в этой святой обители, а затем его назначили в Литву священником в каунасский Благовещенский собор, после чего настоятелем Свято-Никольского храма в Тельшяй и, наконец, в Клайпеду.
В 80-90-е годы, когда началось религиозное возрождение, небольшой храм Всех Русских святых, стал главным центром православия в регионе. Приход быстро рос, обновлялся. Литургию в храме стали служить каждый день. Значительно расширилась сфера интересов общины, осваивались новые направления работы с людьми. При храме начала действовать одна из первых в епархии воскресная школа, открылась общедоступная библиотека православной литературы. Проводились семинары для учителей религии. При содействии о. Антония и прихожан были учреждены два новых прихода: Клайпедский приход святых Веры, Надежды, Любви и Софии и Палангский приход Иверской иконы Божией Матери. Их настоятелями стали служившие в то время во Всесвятском храме протоиерей Илья Шапиро и игумен Алексий (Бабич). Батюшка Антоний скончался 12 ноября 2010 г. после тяжелой и продолжительной болезни.
В 2004 году настоятелем храма был назначен протоиерей Анатолий Стальбовский. При нем значительно изменилось внутреннее убранство: храм был заново расписан, восстановлена позолота иконостаса, установлен новый купол, произведен ремонт вспомогательных помещений. После скоропостижной кончины отца Анатолия 20 апреля 2011 года настоятелем храма стал протоиерей Петр Олехнович. При нем была приведена в порядок территория храма, обновлено покрытие пола.
Кроме уже упомянутых священников в разные годы в храме служили протоиерей Виктор Тимонин (начал там свое служение в 1994 г.), протоиерей Александр Оринка, протоиерей Иоанн Дюлай, игумен Нестор (Шмидт), протоиерей Владимир Артамонов.
В настоящее время настоятелем храма является епископ Тракайский Амвросий (Федукович). Клириками служат протоиерей Петр Олехнович и иерей Антоний Вайнутис.
При храме действует воскресная школа, в которой обучаются около 50 учеников. Кроме Закона Божьего в школе работают различные факультативы: творчества, пения, православной психологии, шахмат, кружок английского и литовского языков, театральная студия.