He is best known for his negative solution of Hilbert's tenth problem (Matiyasevich's theorem), which was presented in his doctoral thesis at LOMI (the Leningrad Department of the Steklov Institute of Mathematics).

[4][5] Being a second-year student, he released two papers in mathematical logic that were published in the Proceedings of the USSR Academy of Sciences.

In 1970, under the guidance of Sergei Maslov [ru], he defended his thesis for the degree of Candidate of Sciences in Physics and Mathematics.

[7] From 1974 Matiyasevich worked in scientific positions at LOMI, first as a senior researcher, in 1980 he headed the Laboratory of Mathematical Logic.

As a teacher, he mentored Eldar Musayev, Maxim Vsemirnov, Alexei Pastor, Dmitri Karpov[10] A polynomial related to the colorings of a triangulation of a sphere was named after Matiyasevich; see The Matiyasevich polynomial, four colour theorem and weight systems.