Not to disagree with Perikles, but both constructs are used here in America. I'm sure that in one region or another there may be a preference for word order, but I have heard and used both of the sentences you proposed.
In fact, each of these sentences conveys the exact same meaning:
Both were born in the same city.
Both of them were born in the same city.
They were both born in the same city.
They both were born in the same city.
|