When a sentence starts with 'Not until', as well as many other phrases, the grammar needed is Inversion, which means using the interrogative form of whatever tense the verb is in. 'begin' is in Simple Present, so 'do' is required. Here are some examples:
Not until John apologizes, will I go out with him again.
Not until the teacher explained it again, did I understand.
Not until I've been working for ten years, will I have saved up enough money to pay off my student loan.
Not until the temperature falls to O degrees C does water turn to ice.
There is a similar question at :Not until ( sentence ) + do (sentence)
but I believe I've explained it slightly differently.
"Not till I got home did I realise my wallet was missing."
(Cambridge Dictionaries Online)