Народився у багатодітній родині відставного унтер-офіцера й полтавської міщанки. Всі 9 дітей отримали освіту, на яку батько, Матвій Стешенко, не шкодував коштів. Іван Матвійович навчався у Полтавській класичній гімназії у 1882-1892 рр. А у 1896 р. закінчив історико-філологічний факультет Київського університету святого Володимира (нині – Київський національний університет імені Тараса Шевченка). У студентські роки входив до мистецького гуртка «Плеяда». Викладав у Київській жіночій гімназії філологічні дисципліни. Також викладав у Фребелівському інституті та на Вищих жіночих курсах. Вільно володів французькою, німецькою, іспанською, італійською, багатьма слов’янськими мовами. Перекладав зарубіжну поезію.
Після жовтневого перевороту 1917 р. став організатором і головою Товариства шкільної освіти. Був обраний до Української Центральної Ради. Як генеральний секретар (з 1918 р. - міністр) освіти здійснив українізацію шкільництва. Був фундатором Українського Народного Університету та Академії Мистецтв.
Для більшовиків І. М. Стешенко із його політикою українізації освіти та відродження національної свідомості був серед ворогів номер один. Ще в січні 1918 р., коли Муравйов захопив м. Київ і влаштував там червоний терор, було видано наказ про вбивство Стешенка. Щоб врятуватись, Іван Матвійович пішки вибрався із захопленого ворогами міста.
Після відставки кабінету В. Винниченка працював головним інструктором міністерства освіти. На цій же посаді залишився і з приходом до влади П. П. Скоропадського. У період Гетьманату І. М. Стешенку пропонують прийняти кафедру української мови у Кам’янець-Подільському університеті.
Тяжкопоранений у м. Полтава в ніч з 29.07 на 30.07.1918 р. невідомими злочинцями. Помер 30.07.1918 р. у лікарні рідного міста. Це не був грабунок, бо злодії навіть не поцікавились речами та вмістом кишень своєї жертви. Похований на Байковому кладовищі у м. Київ.
Це було одне з перших політичних убивств в Україні. 20.12.1923 р. Сергій Олександрович Єфремов (український громадсько-політичний діяч, літературний критик, історик літератури, академік Української академії наук (з 1919 р.), один з творців української журналістики) записав у своєму щоденнику: «Дізнався від Костя Івановича [Товкача] страшні подробиці про вбивство Івана Стешенка. Засудила його на смерть большевистська організація Зіньківського повіту; засуд виконав один з членів цієї організації. Коли б це я не від Костя Івановича чув – я б не повірив: така без краю безглузда, божевільна якась історія. А втім – чи ж божевілля у всяких формах і проявах у нас взагалі бракувало?».
Про те, що вбивство Івана Матвійовича Стешенка – це справа рук більшовиків, підтвердив і нарком держбезпеки УРСР П. Я. Мешик, зазначивши в 1941 р. в постанові на арешт Оксани Стешенко: «Муж Стешенко в прошлом являлся министром просвещения при Центральной раде (убит красными войсками в 1918 году)».
До речі, сам П. Я. Мешик буде арештований у червні 1953 р. за справою Л. Берії. Згодом засуджений Спеціальною судовою присутністю Верховного Суду СРСР до вищої міри покарання – розстрілу з конфіскацією майна, позбавленням військового звання генерал-лейтенантата урядових нагород. 23.12.1953 р. розстріляний.
