My experience is similar. I didn’t just decide one day, “OK, now I believe in rebirth.” I didn’t weigh the merits of one view vs. another view. I didn’t debate with others about it. It just naturally developed on its own with practice and study. I can’t even point out exactly when I became firm about it except to say that it was some time after taking refuge and committing myself to understanding the Buddha’s teachings.
Quite likely, and more intimately at that. 
At Savatthi. There the Blessed One said: "From an inconstruable beginning comes transmigration. A beginning point is not evident, though beings hindered by ignorance and fettered by craving are transmigrating & wandering on. A being who has not been your mother at one time in the past is not easy to find… A being who has not been your father… your brother… your sister… your son… your daughter at one time in the past is not easy to find.
“Why is that? From an inconstruable beginning comes transmigration. A beginning point is not evident, though beings hindered by ignorance and fettered by craving are transmigrating & wandering on. Long have you thus experienced stress, experienced pain, experienced loss, swelling the cemeteries — enough to become disenchanted with all fabricated things, enough to become dispassionate, enough to be released.”
SN 15.14-19