Romanek was born in Chicago, Illinois, the son of Shirlee and Marvin Romanek. He is Jewish. He credits seeing Stanley Kubrick's 2001: A Space Odyssey at the age of nine with inspiring him to become a film director. He experimented with Super 8 and 16mm film as a teenager while attending New Trier High School. There, he studied first with Kevin Dole, a local filmmaker who was already creating a form of music video on his own in the mid-1970s, and then with Peter Kingsbury, a filmmaker who had studied with experimentalists Owen Land, John Luther Schofill, and Stan Brakhage at the School of the Art Institute of Chicago. Both teachers exposed students to works by significant figures of the American avant-garde cinema, such as Maya Deren, Kenneth Anger, and Paul Sharits.
Romanek subsequently attended Ithaca College in Ithaca, New York, and graduated from its Roy H. Park School of Communications with a degree in cinema and photography. He served as second assistant director for Brian De Palma on Home Movies, an autobiographical film De Palma conceived as an exercise for his students at Sarah Lawrence College (having returned to his alma mater as an instructor of film production). On set, Romanek met Keith Gordon, playing De Palma's alter ego. Gordon remembers Romanek's entrance into film production:
||I actually met a lot of people who became important in my life, but Mark being one of the people who was really huge. Mark wasn't even officially one of the students in the class. Mark was kind of like me – he was a film geek. He was from Chicago. And he had followed Brian around on the set of The Fury and gotten a job as a production assistant on that movie. And when he heard that Brian was doing this project, he basically contacted him and said, 'Listen, can I come to New York and basically be like one of the students, even though I'm not technically in the class?' And Brian said, 'Fine.' So Mark became the second assistant director on the film. And he and I just hit it off pretty quickly. We had a similar passion for Stanley Kubrick. He showed me his short films, which I thought were really good and showed a lot of visual flair.
Romanek released his first film, Static, in 1985. It was co-written with Gordon and starred Gordon as a man who claimed he had invented a television set capable of showing a live picture of Heaven. The film achieved something of a cult following in London and led to Romanek's first job at the helm of a music video for the British new wave group The The, who featured on the soundtrack for Static, in 1986.