Народився у багатодітній родині відставного унтер-офіцера й полтавської міщанки. Всі 9 дітей отримали освіту, на яку батько, Матвій Стешенко, не шкодував коштів. Іван Матвійович навчався у Полтавській класичній гімназії у 1882-1892 рр. А у 1896 р. закінчив історико-філологічний факультет Київського університету святого Володимира (нині – Київський національний університет імені Тараса Шевченка). У студентські роки входив до мистецького гуртка «Плеяда». Викладав у Київській жіночій гімназії філологічні дисципліни. Також викладав у Фребелівському інституті та на Вищих жіночих курсах. Вільно володів французькою, німецькою, іспанською, італійською, багатьма слов’янськими мовами. Перекладав зарубіжну поезію.
Ще у студентські роки захопився марксистськими ідеями, очолив радикальну групу студентської громади. Разом з Лесею Українкою, Михайлом Коцюбинським та іншими заснував у 1896 р. у м. Київ групу Українська соціал-демократія. Вже у 1897 р. був заарештований за участь у студентських заворушеннях. П’ять місяців перебував у Лук’янівскій в’язниці. Після був висланий з Києва без права проживання в університетських та губернських містах. Протягом 1897-1900 рр. проживав разом з дружиною, Оксаною Михайлівною (донькою драматурга Михайла Старицького) на Чернігівщині, де займався перекладацькою та літературною працею. Разом з дружиною працював над укладанням словника української мови.
У 1900 р. повертається у м. Київ та продовжив викладати словесність у жіночій гімназії та Музично-драматичній школі Миколи Лисенка. У 1903 р. стає секретарем Правління Київського «Литературно-артистического общества», членами якого були Микола Лисенко, Олена Пчілка та інші культурні діячі. Працює у редакції українського літературного альманаху «Нова Рада». У 1905 р. знову заарештований та відсторонений від педагогічної діяльності.
Був співвидавцем гумористичних журналів «Шершень» (1905) і «Ґедзь». У 1913-1914 рр. був редактором педагогічного часопису «Сяйво». У 1915 р. очолив Тетянинську гімназію для біженців, де навчалися діти галичан, насильно вивезених до м. Київ під час окупації Галичини російською армією. Склав низку програм, методик та підручників, які стали фундаментом для розбудови української освіти у період Української революції.
Був членом Старої Громади, Української соціал-демократичної робітничої партії, Товариства українських поступовців, Товариства Нестора-Літописця, секретарем Українського наукового товариства у м. Київ, дійсним членом Наукового товариства імені Шевченка (з 1917).
Автор ряду праць про І. П. Котляревського, за одну з яких у 1898 р. отримав нагороду Петербурзької Академії Наук, та біографічних розвідок про Панаса Мирного, Марка Вовчка, Михайла Коцюбинського, Василя Стефаника, Михайла Старицького та ін. Його перу належать збірки поезій «Хуторні сонети» (1899), «Степові мотиви» (1901), оповідання «На заводі», драма «Мазепа). Автор популярних пісень «Вже воскресла Україна», «Гей не дивуйтесь, добрії люди». Перекладав українською мовою твори Овідія, Фрідріха Шіллера, Джорджа Байрона, П’єра-Жана Беранже та ін.
Після жовтневого перевороту 1917 р. став організатором і головою Товариства шкільної освіти. Був обраний до Української Центральної Ради. Як генеральний секретар (з 1918 р. - міністр) освіти здійснив українізацію шкільництва. Був фундатором Українського Народного Університету та Академії Мистецтв.
Для більшовиків І. М. Стешенко із його політикою українізації освіти та відродження національної свідомості був серед ворогів номер один. Ще в січні 1918 р., коли Муравйов захопив м. Київ і влаштував там червоний терор, було видано наказ про вбивство Стешенка. Щоб врятуватись, Іван Матвійович пішки вибрався із захопленого ворогами міста.
Після відставки кабінету В. Винниченка працював головним інструктором міністерства освіти. На цій же посаді залишився і з приходом до влади П. П. Скоропадського. У період Гетьманату І. М. Стешенку пропонують прийняти кафедру української мови у Кам’янець-Подільському університеті.
Тяжкопоранений у м. Полтава в ніч з 29.07 на 30.07.1918 р. невідомими злочинцями. Помер 30.07.1918 р. у лікарні рідного міста. Це не був грабунок, бо злодії навіть не поцікавились речами та вмістом кишень своєї жертви. Похований на Байковому кладовищі у м. Київ.
З приходом до влади більшовиків ім’я І. М. Стешенка було записано до «українських буржуазних націоналістів» і викреслене із історії. Його дружина дитяча письменниця О. М. Стешенко-Старицька та її старша сестра письменниця, театральний критик та громадська діячка Л. М. Старицька-Черняхівська були арештовані влітку 1941 р. та вислані до Казахстану. Л. М. Старицька-Черняхівська померла в дорозі до концтабору. Її тіло було викинуто з потягу. Життя О. М. Стешенко-Старицької закінчилось у концтаборі у 1942 р.
Вже після отримання Україною Незалежності ім’я І. М. Стешенка було присвоєно Крем’янецькій приватній українській гімназії. А 28.02.2018 р. Кабінетом Міністрів України засновано в числі академічних стипендій імені державних діячів першого українського уряду для студентів та курсантів закладів вищої освіти державної форми власності, які здобувають вищу освіту за освітнім рівнем магістра стипендію імені Івана Стешенка (Освіта/Педагогіка).
13.09.2008 р. на будинку Великобудищанської загальноосвітньої школи І-ІІІ ступенів була встановлена меморіальна дошка на пошанування пам’яті І. М. Стешенка. В стінах цієї школи, на той час земської, у червні 1918 р. перший міністр освіти УНР читав лекції з українізації учительства.
