Народився 31 січня 1960 року в м. Києві. Після закінчення фізико-математичної школи вступив на навчання у 1976 році до Київського державного університету на факультет кібернетики (спеціальність ‑ прикладна математика).
1981 — 1984 роки ‑ працював в Спеціальному конструкторському бюро математичних машин і систем Інституту кібернетики імені В.М. Глушкова (нині ‑ Інститут проблем математичних машин і систем НАН України) на посаді інженера, потім був командиром радіо-локаційного взводу в армії, в протиповітряних військах. Після армії поступив в аспірантуру Інституту кібернетики імені В.М. Глушкова, науковий керівник – проф. Ю.В. Капітонова.
О.О. Летичевський працював в Інституті кібернетики після закінчення аспірантури. Він також працював в компанії ЛітСофт програмістом та архітектором програмних систем. Останні двадцять років О.О. Летичевський працює в Інституті кібернетики як науковий співробітник. Наразі очолює відділ теорії цифрових автоматів.
У 2006 році захистив кандидатську дисертацію за темою «Верифікація та тестування інтерактивних систем специфікованими базовими протоколами» та в 2016 році докторську – тема «Символьні методи в тестуванні та верифікації високонадійних програмних систем».
Працює над сучасними програмними системами та провідними алгебраїчними теоріями – алгебраїчне та інсерційне програмування, кібербезпека та розробка супернадійних систем, працює в області використання формальних методів у верифікації та тестуванні програмного та апаратного забезпечення, в тому числі блокчейн-платформи та розподілені системи.
Роботи О.О. Летичевського були використані компанією MOTOROLA в галузі формальної верифікації. Він співпрацював з багатьма компаніями із США, був контрактором Міссурійського університету (Rolla). Розробки О.О. Летичевського з кібербезпеки та модельних методів впроваджено в роботу низки підприємств України, зокрема, в галузі ядерної енергетики.
О.О. Letychevsky has more than 70 scientific works, 1 monograph, 4 copyright certificates.
Laureate of the State awards of Ukraine in the field of science and technology in 2019 for the work "Ensuring the functional security of critical information and control systems." (Decree of the President of Ukraine of January 13, 2020 № 4).