Such languages are uncommon but not unattested. However, they are more common than prepositional SOV languages and are present in a number of unrelated families around the world.
This WALS map shows us that in general, the order of object and verb and adposition and noun phrase is very highly correlated. In the map, postpositional VO languages are the group with the third highest number of total languages, but they are less than a tenth as common as the most frequent types.
Postposition / OV 472
Preposition / VO 454
Postposition / VO 41
There are some parts of the world such as West Africa where there are many SVO languages with postpositions. There seems to be a cluster of them around Côte d'Ivoire and Ghana. I think the languages in question are proven or suspected to be Niger-Congo languages. The westernmost group of these languages has both VO and OV languages as well as some intermediate types like SOVX languages and postpositional VO languages.
Another example of a postpositional VO language is Finnish. I think Proto-Uralic is generally reconstructed as having verb-final word order. However, many of the modern groups of Uralic languages have SVO word order.
There are a few cases of languages with verb-initial word orders with postpositions. One such example is Yagua. Yagua is an interesting case because the verbs are very highly inflected, but the nouns are not.