The problem is usually caused due to incorrect permissions to storage folder mostly.
If you use Laravel installer, setting up a new project would be super easy. It will setup the correct permissions and other configurations, like generating a key, etc.
For all the newcomers having this problem, please consider using Laravel Installer, it will save you a lot of time. Please read the "Via Laravel Installer" section here on: https://laravel.com/docs/5.3/installation