Martin Matejka pochází z lázeňského městečka Trenčianských Teplic, kde jsou jeho rodiče dodnes známi pod svými trampskými přezdívkami Hasan a Benita. Až do puberty měl problémy s nadváhou, zároveň byl nejlepším žákem a předsedou třídy, zúčastňoval se nejrůznějších soutěží, recitoval, zpíval chlapeckým sopránem... prostě byl prototypem vzorného hocha. Ke konci základní školy po zápalu plic zhubnul a v odbobí mutování přestal zpívat, v recitačních soutěžích však pokračoval. Na trenčínském gymnáziu se spolu s o rok starším spolužákem a dnešním kolegou Martinem Velikým začal navíc věnovat amatérskému divadlu ve spolku DDT (Diskrétne divadlo Trenčín).
Po maturitě (k vlastnímu údivu absolvoval třídu s elektrotechnickým zaměřením) chtěl jít původně na pedagogickou fakultu, ale nakonec následoval příkladu již zmíněného Martina Velikého a přihlásil se na katedru alternativního a loutkového divadla pražské DAMU, kam byl přijat. Ve druhém semestru ho - po doplnění chybějících zkoušek - kooptovali o ročník výše, takže školu nakonec skončil se skupinou, která po absolutoriu nastoupila do Dejvického divadla a posléze do Divadla v Dlouhé. Ze školy si Martin Matejka přinesl otevřenost k různým stylům práce s různými režiséry. Baví ho bezprostřední kontakt s diváky, jehož se mu vrchovatě dostává zejména při dětských představeních, rád hraje s loutkou či rekvizitou, ale nezříká se ani tzv. klasické činohry (jako správný blíženec se nikdy nedokáže definitivně rozhodnout).