I was creating a SharePoint add-in with Visual Studio and testing with SharePoint Online, but I needed to test it on my SharePoint 2013 on-premise farm.
After uploading the .app file to my on-premise App Catalog, SharePoint complained about the validity of the App Package.
After some fiddling and researching it turns out that all I needed to do was change the SharePointMinVersion from 126.96.36.199 to 188.8.131.52 in AppManifest.xml.
After repackaging and uploading to my App Catalog, SharePoint was now showing my app the love it deserves. Valid App Package was now a Yes.