Agile methods typically don’t cover the early stages of projects very well. They often assume you are ready to start gathering requirements as user stories, or that you even have some candidate features or stories magically ready to go. This is shown by the scope coverage diagram below.
 

 
 

Yet for all but the smallest, most process-light organizations, there are stages of envisioning, feasibility, and setup that happen before we are ready to jump into requirements gathering. This is where many companies come unstuck with agile. Either they jump straight to stories and miss out the early project stuff and suffer disoriented stakeholders and disengaged project offices. Or they go too heavy with the upfront chartering and scope definition, create brittle plans and lose some of the advantages of adaptation and iterative development.

The following diagram is a good place to consider starting from. It combines some of the bare necessities from a traditional approach that will satisfy the project office. Yet it does not go too far into Big Design Up Front (BDUF) to create problems or consume too much time that could be better spent working directly with the business to determine their requirements via collaborative development.

The overall duration is short, just 15% of the likely (guestimated) project duration, but yields lightweight versions of the key deliverables familiar to the PMI process police. We get stakeholders informed and engaged, the project office placated, and the bulk of the project duration dedicated to iterative development. 

Instead of a Work Breakdown Structure (WBS) I would recommend a candidate prioritised Feature List or prioritised Story list.

Kick-Off meetings using the Design The Product Box exercise, or Shape the Poduct Tree are a great way to start identifying candidate features and then follow them up with Feature Discovery Workshops. The length and number of feature workshops will vary depending on the size and complexity of your project. A three month web project with a team of three people might be scoped in a day or two. Yet a three year project with 30 people will take longer to drive out all the candidate features.

I am actually quite a fan of the early project deliverables like Project Charters since they explain important W5+ (What, Why, When, Who, Where + How) elements of a project, but believe these documents don’t have to be verbose or costly to create.

Instead cover the basics, get people onside and the whole endeavour will go quicker than if you try to start without these things and have to catch people up later.