I'm applying to history Ph.D programs without a history major, or even a history minor. Rather I majored in political science with an emphasis on theory, then went on to law school. I've only applied to "Top 50" programs. The majority of them mentioned looking for a major in history OR a related/complementary field, which most seem to think includes political science. The one program with an express requirement did not require a history major, but just referred to a certain number of credits in history as a mandatory qualification. I fell just short ofthat number, emailed the head of graduate studies, and was essentially told that even that number was flexible (unless my previous experience with history had been Zero), it sounded like I had plenty of exposure to history and not to worry about that particular item. I can't speak for programs other than those to which I applied, but I imagine they are fairly representative.
Of course we'll see how it works out for me.