So it turns out I hadn't updated my Fedora installation for over two years (protip: don't run Fedora on a server kids) so I did a quick series of upgrades and went from Fedora 21 to Fedora 25.
Unfortunately that means that my PostgreSQL database was at version 9.3 but the installed software was version 9.5.
So can you upgrade from 9.3 to 9.5? No. But it's not impossible either.