iPhone storage is full while iCloud is empty
The biggest thing that takes up storage is photos. If you're running iOS 9 or later, then go to Settings -> iCloud -> Photos and enable iCloud Photo Library. Then, make sure optimize iPhone storage is checked. Also, delete any apps that you may not use. Pay close attention to games. They eat up the most space. Switching to a streaming music service like Music or Spotify will also let you free up space by deleting music on your device.