Those are grammatical utterances but not quite natural. A native speaker, in conversation, is not likely to choose either of those patterns, which use a noun phrase, but instead would treat waiting as a verb and say something like
That was when I started waiting for him.
That was when I began waiting for him.
That was when I began to wait for him.
Alternatively, the speaker would use the noun wait:
That was the beginning of my wait for him.
That was when my wait began.
In a story you might read:
That was when the waiting began.
especially if the theme of the story is her waiting for him in a number of ways, sometimes literally, sometimes figuratively, over the course of a long relationship.