Two weeks after his dismissal, Holovak signed as a scout with the fledgling Patriots, then was named an assistant under Lou Saban on March 29, 1960. After a 5–9 record that year and a 2-3 start in 1961, Saban was fired on October 10 and replaced by Holovak. His first game as Patriots coach was a 31-31 tie (the first in Patriots history) with the Houston Oilers. Finishing with a 9–4–1 record, Holovak matched that record the following year, earning him a new three-year contract, with an option for another year.