It all depends. Sure, a major is preferable. Can you indicate in your SOP that you fell in love with history and didn't have time to pursue a major in it by then? Can you say that you became overwhelmed with a passion for Euro history and just knew that it was exactly what you wanted to do for the rest of your life? Are your recs from history profs who say you are a promising historian?
Your double major and double minor are very impressive, but I'm worried an adcom would think "This guy doesn't know what the hell he wants to do." You need to demonstrate a drive to study history. Prove it to them. If you can accomplish that, the difference in preparation between a major and a minor will be insignificant.
The above poster is correct in that he said it is more flexible in the humanities than the sciences-- in the sciences there are just certain classes you have had to take or else you're up shit creek. You have a little latitude here, but you gotta hit in every way possible that Euro history is your passion and you are fully dedicated to it.
On the other hand, grad admissions are so tough, that it comes down to you and another candidate, and he has a major, adcoms might say "fuck it, lets take the dude with the major."