Lost my iPhone 5s, can I get non-iMessage texts back after I replace it? I recently lost my iPhone, and have some important non-iMessage texts from android devices on it -- is it possible to restore these after replacing the phone, or am I out of luck here?
iCloud backups do include any SMS and MMS messages on your device. The same is true if you back up to your computer using iTunes.

When you get your new phone, your messages will be there if you restore from one of those backups.