Происхождение рода Тухачевских окутано легендами в не меньшей степени, чем его трагический конец. В Энциклопедическом словаре Брокгауза и Ефрона о Тухачевских говорится следующее: «Дворянский род, происходящий, по сказаниям старинных родословцев, от выехавшего в Чернигов из цесарской земли при вел. кн. Мстиславе Владимировиче графа Индриса, в крещении Константина. Его потомки в XV в. переселились из Чернигова в Москву и приняли фамилию Тухачевские. В XVI и XVII в. Тухачевские служили по Брянску, а во второй половине XVII в. были стольниками, стряпчими и т. п. Николай Сергеевич (1764–1832) был тульским губернатором, его сын Николай Николаевич — наказным атаманом донского казачьего войска (1846). Род Тухачевских внесен в VI часть родословной книги Московской губернии».
К этой довольно скупой справке можно добавить, что, по семейным преданиям, легендарный основоположник рода Тухачевских граф Индрис был венгерского происхождения. Любопытно, что эта легендарная личность считалась родоначальником не только Тухачевских, но и еще трех русских дворянских фамилий, в том числе такой знаменитой, как Толстые, давшей России и миру трех великих писателей — Алексея Константиновича, Льва Николаевича и Алексея Николаевича. В том же «Брокгаузе и Ефроне» о Толстых читаем: «Графский и дворянский род, происходящий, по сказаниям старинных родословцев, от мужа честна Индриса, выехавшего, "из немец", из цесарской земли, в Чернигов в 1353 г., с двумя сыновьями и дружиною из трех тысяч человек; он крестился, получил имя Леонтия и был родоначальником нескольких дворянских фамилий. Его правнук, Андрей Харитонович, переселился из Чернигова в Москву и, получив от вел. кн. Василия Темного прозвище Толстой, стал родоначальником Т.». Заманчиво предположить, что граф Индрис обладал литературными способностями, передавшимися его потомкам. Тухачевский, конечно, не Толстой, однако его приказы, выступления и статьи отличаются определенным, присущим только ему стилем и написаны хорошим русским языком, что, в частности, способствовало их популярности как среди военной, так и среди гражданской публики.
Более подробные сведения о происхождении родов Толстых и Тухачевского можно найти в капитальном труде Н. И. Гусева «Лев Николаевич Толстой. Материалы к биографии». Там цитируется «старинный родословец» — роспись, которую в 1686 году Толстые вместе со многими другими служилыми людьми подали в Палату родословных дел Разрядного приказа: «В лета 6861-го (то есть, в 1352 или 1353 году от Р.Х. — Б. С.) прииде из немец ис цесарского государства муж честного рода именем Индрос з двумя сыны своима с Литвонисом да с Зигмонтеном а с ними пришло дружины и людей их три тысячи мужей и крестися Индрос и дети его в Чернигове в православную христианскую веру и нарекоша им имена Индросу Леонтием а сыном его Литвонису Константином а Зигмонтену Федором; и от Константина родился сын Харитон а Федор умер бездетен, о сем пишет в летописце Черниговском». Первый граф Толстой, Петр Андреевич, один из славных «птенцов гнезда Петрова», который, скорее всего, и составил роспись, в своей автобиографии прямо писал: «В лето 1352-е прародитель мой выехал из Германии в Российское государство».
Далее в толстовской росписи сообщалось, что правнук Индроса Андрей Харитонович «приехал из Чернигова к Москве к великому князю Василию Васильевичу всея России. И великий князь Василий Васильевич всея России прозвал его Толстым, с того пошли Толстые».
Таким образом, имя у прародителей Тухачевских и Толстых практически одинаковое, Индрис-Индрос, что с большой долей уверенности говорит, что это был один и тот же человек. Но вот о времени его появления в Черниговской земле родовые предания сообщают по-разному. Если учесть, что Мстислав Владимирович был черниговским князем в 1026–1036 годах, то в венгерское происхождение Индриса верится с трудом. Ведь тогда Венгрия в «цесарскую землю», то есть «Священную Римскую империю германской нации» еще не входила. Больше доверия заслуживает толстовская версия о появлении Индроса с сыновьями и дружиной в Чернигове в 1352 или 1353 годах. Правда, Черниговская летопись, на которую ссылаются Толстые, до нас не дошла, и вообще нет никаких данных, что после разгрома Чернигова татарами в 1239 году и фактической гибели княжества там велось хоть какое-то летописание. Возможно, это обстоятельство и побудило Тухачевских отнести прибытие Индриса в Чернигов к домонгольской эпохе. Но в этом случае совершенно непонятно, что делали потомки Индриса целых четыреста лет, до времен Василия Темного, когда их имена появляются, наконец, в русских летописях, грамотах и разрядных книгах.
Что же касается мнения о том, что Индрис был выходцем из Германии, то оно не более основательно, чем мысль о его венгерском происхождении. Недаром С. М. Соловьев в «Истории России с древнейших времен» считал почти все родословные росписи «сочиненными», а советский историк С. Б. Веселовский несколько дипломатичнее говорил о «злоупотреблении вымыслом» в генеалогических сочинениях.
Если верно предание, что предок Тухачевских прибыл из Чернигова в Москву в XV веке, в княжение Василия Темного, то можно предположить, что он был братом того, кого великий князь наградил прозвищем Толстой (видно, по причине тучности и чревоугодия). В ту пору Черниговская земля входила в состав Великого княжества Литовского, где православные были ущемлены в правах по сравнению с католиками. Поэтому многие православные шляхтичи предпочитали отъезжать к московским великим князьям, рассчитывая, что служить у единоверцев будет легче.