Some licenses for Office 2007 allow installation on more than 1 device. Then there is no need to buy a new version. And if you uninstall it from the old machine and it's a retail version, you can use the same license on your new machine.
Anyway, https://products.office.com/en-us/buy/compare-microsoft-office-products shows that Office 2016 Professional comes with Publisher and is a one time purchase.
Office 2013 Professional has Publisher also; you can buy it for example via http://www.amazon.com/s/ref=nb_sb_ss_i_1_12?url=search-alias%3Daps&field-keywords=office+2013+professional&sprefix=office+2013+%2Caps%2C290
https://products.office.com/en-us/buy/office shows that Publisher 2016 is available as a separate product. You can add that to a Office 2016 Home and Student edition; the combination is cheaper.
Microsoft is chystal clear, I'd say. So it's somewhat strange you couldn't find it.
If you prefer to buy in a physical shop in stead of via the web, be sure to find a shop that is just as crystal clear.
Looking to put MS Office (with Publisher, don't care about Outlook or Access) on a new computer. Want to work on my own machine, not in the Cloud, and purchase one time, not by subscription. Can't seem to get a crystal clear answer as to whether Office 2013 and 2016 are even available this way any more. (I've been using 2007 up til now). What's the story?