In my experience, it really depends on the leather and styling of the shoe. I've had shoes that did that and stretched out after one or two wears, and ones that never did.

Is the leather soft and supple to the touch? If so, it will likely stretch out and be more comfortable soon. If it's got a binding or stitch line near the edge, though, I'd pass. Those kinds of shoes almost never stretch out.

I might also use Bandaid's Blister Block as you stretch the shoe out. It works as a thin waxy cushion between you and the shoe which cuts down on any friction.

Also, what Ele said. :)

Depends how stiff the leather is. My Ecco flats rubbed my big toe bone at first, but they are soft and supple so I kept them and they have stretched reasonably well. On the other hand, shoes that are extremely stiff and inflexible don't stretch no matter what and can potentially cause some pretty agonizing pain by the end of the day. I find this to be most true of patent leather. I have seen soft patent leather, but for the most part it tends to be much less forgiving than matte leather.

If they are leather it can be stretched, but if it's synthetic I'd take them back.

YOu might also ask the store at which you bought it whether they will stretch it for you and if you can return it after it's been stretched. Nordstrom's does this and it worked wonders for a pair I own.