What version of WordPress are you using? Are you using the latest version (4.5.2)?
You could try to increase your maximum upload size. There are several ways to do this, but you could add the following line to your wp-config.php:
define( 'WP_MEMORY_LIMIT', '64M' );
Have you verified your file permissions and you are able to write to your uploads folder?
If that still doesn’t work, I would try deactivating all plugins. If that resolves the issue, reactivate each one individually until you find the cause.
If that does not resolve the issue, try switching to the default theme for your version of WordPress to rule-out a theme-specific issue (theme functions can interfere like plugins).
