Since Amazon Fire Phone is an Android based phone, you have the possibility to install APK files from Play Store and Amazon Store. Most likely, it will have Amazon App Store, you can use the Play Store as well. Search for "Cheap International Calls" and you should find an application which has an icon similar to a blue heart.
To get a better overview about this, use the following link from Play Store: https://play.google.com/store/apps/details?id=com.rebtel.android
