Первоначально на месте церкви находились римские бани, устроенные над водопроводом и подземным источником, на фундаменте которых была устроена раннехристианская базилика. Строительство настоящего храма относится к первой половине XI века. Церковь была освящена в честь Пресвятой Троицы, впоследствии, благодаря жертвователю, получила народное имя «Сотира Ликодиму».
Здесь находился Спасо-Никодимовский монастырь. С 1202 года — женский католический монастырь, а с 1204 года — бенедиктинский. В османский период храм являлся католиконом православного мужского монастыря.
Храм подвергался разрушениям несколько раз, например, в 1687 году с вступлением в город сил венецианцев под предводительством Франческо Моросини. Часть стен и братский корпус монастыря были разрушены сильным землетрясением в 1701 году, но церковь почти не пострадала. Оставшиеся строения монастыря были уничтожены в 1780 году по приказу турецкого правителя Афин Али Хасеки, занимавшегося строительством новых городских стен в этом районе. С этого момента храм становится приходом монастыря Кессариани.
Во время войны за независимость Греции, в 1827 году, здание снова понесло урон — в него попало несколько снарядов с Акрополя. В результате рухнул купол и северо-восточная часть. На оставшейся невредимой алтарной стене сохранились фрагменты византийских фресок.
24 февраля (8 марта) 1833 года Обер-прокурор Святейшего Синода князь П. С. Мещерский представил Синоду пожелание Императора Николая I, «чтобы в Греции находилась российская духовная особа в качестве священника нашей миссии». Уже 4 (16) марта 1833 года был утверждён штат временной церкви при российском Императорском Посольстве в Греции. В июле в Афины отправилось духовенство.
Первоначально посольской церковью стал Преображенский храм XI века, известный также как Котаки или Святая София, в квартале Плака. Церковь была восстановлена в 1834—1837 годах на русские средства.
В 1847 году храм Сотира Ликодиму был куплен российским правительством. Инициатором его восстановления был его настоятель архимандрит Антонин (Капустин). Научная реставрация проводилась на средства Министерства иностранных дел под руководством архитектора Р. И. Кузьмина при участии И. В. Штрома. Работы велись до 1854 года.
При восстановлении был сохранён первоначальный план храма, открыты древние фрески и заложенные проёмы. В подвалах храма архимандрит Августин произвёл археологические раскопки. В 1850 году в том же стиле, что и церковь была построена колокольня.
Освящение храма состоялось 6 (18) декабря 1855 года. Его возглавил архиепископ Мантинейский и Кинурийский Феофан.
Вскоре после освящения из-под пола церкви стала поступать вода из подземного источника и пришлось разбирать фундамент. В 1885 году в самом храме начались протечки, в связи с чем архитектор В. Шиллер, несмотря на протесты художника Людвига Тирша, понизил купол на полметра.
При храме была библиотека с множеством старинных русских книг.
Для поддержания в нормальном состоянии храма в 1919 году был основан Союз русских православных христиан в Греции. В 1924 году, после признания Грецией СССР община отделилась от посольства и присоединилась к Афинской Архиепископии со статусом «параклиса».
В 1954 году, по ходатайству Великой Княгини Елены Владимировны, Принцессы Греческой и Датской, была восстановлена древняя высота купола. В 1999 году на средства греческого правительства была отреставрирована колокольня.
В 1955 году во время работ, в восточном углу храма, было обнаружено кладбище с костницей, где, согласно источникам, были похоронены киевляне, проданные татарами в Константинополе. Останки перенесены в крипту церкви.
В настоящее время храм относится к Афинской Архиепископии Элладской Православной Церкви. Является приходом русскоязычной общины Афин.