1901年4月7日、メドニヤンスキ・マリアはハンガリー王国(現ハンガリー)の首都ブダペストで労働者階級の家庭に生まれた[4]。少女時代に両親が相次いで死去したことから若くして職に就くことを余儀なくされ[7][4]、15歳のときにブダペストにあるハンガロ・イタリアン銀行で銀行員として働き始めた[2]。やがて仕事の休憩時間にレクリエーションとして同僚らと卓球をするようになり[4]、1925年にハンガリーのスポーツソサエティである「ハンガリーアスリートクラブ(ハンガリー語: Magyar Testgyakorlók Köre、略称:MTK)」に加入して本格的に卓球を始めた[6]。当時のMTKには後に世界チャンピオンとなるバルナ・ヴィクトル、メチュロヴィチュ・ゾルタン、サバドシュ・ミクロシュ(いずれもハンガリー)などの有力な卓球選手が在籍していた[2]。