You get 5gb of iCloud backup space for free. You can either buy more space, or reduce the size of the backup. For most people, their Camera Roll is the single biggest user of iCloud storage space. Transfer photos and videos from the iPhone to your computer, and delete the ones you don't really need to carry around with you from the iPhone.
Here's Apple's overview article:
https://support.apple.com/kb/PH12519 It'll explain what's stored in the iCloud backup, and what you can do to manage the space you use. This article
https://support.apple.com/en-us/HT201656 will show you how to view the way you're using the iPhone's on-board storage space.
While you can definitely get around the problem by backing up to iTunes, in my experience, most people who depend on iTunes for backup don't backup nearly often enough. When iCloud backup is working, you'll be backing up automatically on a daily basis.