She was born in Bytom, Poland, in 1985. As a toddler, she emigrated with her mother to the United States. She grew up in New Jersey, where she also graduated from her first schools. The city she grew up in, because of its industrial landscape, reminded her of… Bytom. Majok is a graduate of the University of Chicago and Yale University (Yale School of Drama). She also went to the famous Juilliard School in New York.
Since her early days, she loved to write. However, she was also forced by her family situation to indulge in quieter artistic activities such as drawing or writing stories – little Martyna, together with her mother and sister, were dependent on the moods of her aggressive stepfather. She was persuaded to take part in a competition for a theatre play by her teacher. She won but went to the theatre for the first time only as an adolescent – it was the musical Cabaret in Studio 54, in the building of the legendary club frequented by Andy Warhol, the same place where Giorgio Armani threw birthday parties. The show, directed by Sam Mendes, captivated Majok to such a degree that she decided to go into theatre. As she said:
It was a fantastic play – sad, funny, sexy, touching – I laughed, cried and was delighted.