How can I find an iOS app I had installed once but since deleted?
If your old phone and new phone are both iPhones, then all you need to do is check the purchase history under your Apple ID to re-download it.

To do this:


Launch the App Store app on your iPhone
Tap on Updates
Tap on Purchased


You will now be able to access your purchase history and, should even be able to filter by the Not on This iPhone tab.

If you can't find the app in your history, then it's possible that it's no longer available on the App Store. If that's the case, you may be able to re-install it from iTunes on your computer, especially if you have Time Machine backups (assuming you're on a Mac).