Born in Prague, Hřebejk studied together with his classmate Petr Jarchovský at high school. Now Jarchovsky is a frequent collaborator as a screenwriter. From 1987 to 1991, Hřebejk studied screenplay and dramaturgy at FAMU, an arts college in Prague for film and television.
During his FAMU studies, Hřebejk directed and produced two short films, Everything You Always Wanted to Know About Sex But Were Afraid to Experience (1988) and 1948 AD (1989), to a script written by his classmate Petr Zelenka. His professional directorial debut was a short film for Czech TV, You Do Nothing Because You've Got No Good Reason (1991). His films caught the attention of viewers and critics, and entered student film festivals.
Together with Petr Jarchovský, during his FAMU studies, he wrote a comedy screenplay, inspired by his background at a pioneer summer camp, Let's Sing the Song Naked-on. This screenplay was filmed in 1990 as a full-length feature by director Ondřej Trojan and cameraman Asen Šopov.