How much free storage space do you have on your iPhone? (Settings > General > iPhone Storage)
How much storage is Messages using on your iPhone. (Settings > General > iPhone Storage > Messages)
In Settings > Apple ID, iCloud… > iCloud is Messages turned on or off?
On your Mac in Message > Preferences > General what is Keep messages set to?
On your Mac in Message > Preferences > iMessage > Settings is "enable Messages in iCloud checked (✔)?