Can I view iMessage history from an iPhone set up as a new device? I set up a new iPhone as a new device (not from a backup) but using my same Apple ID for iCloud and so on. Can I view my old iMessages on this phone?

If I restore from backup, the messages appear. I set up the phone as a new device because I was getting some strange syncing behaviors.

I would really like to have my old conversations available. Any way to do this? Are they in iCloud somewhere? Thanks!
You can only restore your data (messages are part of your data) by restoring from backup. That should work fine, assuming that the backup iOS version and the new phone iOS version are the same. If your data backup is from an earlier iOS revision than your new phone, all bets are off. 

Restoring your data from backup shouldn't introduce sync problems as the operating system of the phone is not part of the backup scheme.